题目链接：

题意：

       哈利珀特想要抢劫银行，他有n个目标银行，而且为避免被捕风险，他的朋友为他计算出了他被抓风险一定要低于np，否则抢劫会失败，给出目标银行能被抢劫的一定金额数和在该银行抢劫被抓到的概率，问哈利在不被抓的情况下，抢劫的钱最多能有多少？

案例：

       Sample Input

       3

       0.04 3

       1 0.02

       2 0.03

       3 0.05

       0.06 3

       2 0.03

       2 0.03

       3 0.05

       0.10 3

       1 0.03

       2 0.02

       3 0.05

       Sample Output

       Case 1: 2

       Case 2: 4

       Case 3: 6

分析：

       背包问题，打表。

       做一个简单转换，把银行总钱sum作为背包容量，把（1-p[i]）作为重量W，背包问题模版可以参考紫书《算法竞赛入门经典》。 然后倒叙，找出可以偷出的最多的钱。

源代码：

1 #include
     
       2 #include
      
        3 int n,a[105],sum,count; 4 double np,p[105],dp[10005]; 5 double max(double x,double y) 6 { 7     return x>y?x:y; 8 } 9 void judge()10 {11     int j,k;12     memset(dp,0,sizeof(dp));13     dp[0]=1;14     for(k=1;k<=n;k++)//记录抢劫价值j被捕的概率15         for(j=sum;j>=a[k];j--)16         {17             dp[j]=max(dp[j-a[k]]*(1-p[k]),dp[j]);18         }19     for(count=sum;count>=0;count--)20         if(dp[count]>1-np)21             break;22 }23 int main()24 {25     int T,cnt=0;26     scanf("%d",&T);27     while(T--)28     {29         sum=0;30         scanf("%lf%d",&np,&n);31         for(int i=1;i<=n;i++)32         {33             scanf("%d%lf",&a[i],&p[i]);34             sum+=a[i];//总价值35         }36         judge();37         printf("Case %d: %d\n",++cnt,count);38     }39     return 0;40 }