题意：

　　第一行第一个小数，是这个人被抓住的概率最大不能超过这个数，第二个是有N个银行。一个整数和小数分别为这个银行有多少钱和被这个银行

抓住的概率。求出这个小偷在不超过自己抓住的最大概率中抢更多的银行。

 

坑爹：

　　f 数组 初始化为0 ，但是 f [0] 要为1，因为不抢任何银行的时候永远是成功的。所有银行的钱数加起来是“背包”的容量，不被抓的概率是价

值。

 

解法：

　　套用01背包的状态转移方程，解出不被抓住的概率，然后用1减去它，再和被抓住的概率比较。

 

1 #include
      
        2 using namespace std; 3  4 const int maxn = 10000 + 10; 5 int price[maxn]; 6 double chance[maxn]; 7 double f[maxn]; 8 int sum; 9 10 double max(double a,double b)11 {12     return a>b?a:b;13 }14 15 void ZeroOnePack(int cost,double weight)16 {17     int j;18     for(j=sum; j>=cost; j--)19     {20         f[j]=max(f[j],f[j-cost]*weight);21     }22 }23 24 int main()25 {26     int T;27     cin>>T;28     while(T--)29     {30         int N;31         double P;32         cin>>P>>N;33         int i;34         P=1-P;35         36         sum=0;37         for(i=1; i<=N; i++)38         {39             cin>>price[i]>>chance[i];40             chance[i]=1-chance[i]; 41             sum+=price[i];42         }43         44         memset(f,0,sizeof(f));45         f[0]=1.0;46         for(i=1; i<=N; i++)47         {48             ZeroOnePack(price[i],chance[i]);49         }50 51 52         for(i=sum; i>=0; i--)53         {54             if(f[i]>P)55             {56                 printf("%d\n",i);57                 break;58             }59         }60         61     }62     return 0;63 }