学步园

这题开始我拿了，不知怎么下手，但幸好这题是在背包这里，提示了我，肯定能用背包解，但显然概率不能作为一维数组的下标，所以只能找价值来当一维数组下标，而要不失败，即全部成功，求全部成功的概率就行了。其实仔细想想0-1背包的二维中两个下标是对称的。

还有0要初始化为1，因为如果神马都不抢成功率为1

#include<stdio.h>
#include<string.h>
double dp[10005],W,w[10005];
int n,v[10005],ma;
double max( double a,double b )
{
       return a > b ? a : b;
}
void DP( )
{
     memset( dp,0,sizeof( dp ) );
     dp[0] = 1;//因为抢0是%100的安全，所以这里要置为0 
     for( int i = 1; i <= n; ++i )
          for( int j = ma; j >= v[i]; --j )
               dp[j] = max( dp[j-v[i]] *( 1 - w[i] ) , dp[j] );
 }
int main( )
{
    int t;
    scanf( "%d",&t );
    while( t-- )
    {
           ma = 0;
           scanf( "%lf%d",&W,&n );
           W = 1 - W;
           for( int i = 1; i <= n; ++i )
                scanf( "%d%lf",&v[i],&w[i] ),ma += v[i];
           DP( );
           int m = 0;
           for( int i = 0; i <= ma; ++i )
                if( dp[i] >= W )
                    m = i;
           printf( "%d\n",m );
           }
    return 0;
}