题目链接：

经典DP练习题，自己的水平有限，参考了网上其他的答案。

01背包问题，如何选择背包容量和物品的价值在这里是比较困难的地方，把银行的钱当做背包，把概率当做价值，总容量为所有银行的总钱数，求不超过被抓概率的情况下，最大的背包容量是多少。这样的决策在AC过程中起到了比较大的作用。

这里有一个误区，被抓的概率不是简单的相加，而是符合概率论的相乘，p = (1-p1)(1-p2)(1-p3) 其中p为最大不被抓概率，p1，p2，p3为各个银行被抓概率。因为在测试样例中看不到这样的关系，所以这是需要警惕的点。

代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 struct bag 6 { 7     int v; 8     double p; 9 }Bag[10010];10 double dp[10010];11 12 int main()13 {14     int T,N;15     double p;16     scanf("%d",&T);17     while(T--)18     {19         scanf("%lf %d",&p,&N);20         int sum = 0;21         for(int i = 0; i < N; i++)22         {23             scanf("%d%lf",&Bag[i].v,&Bag[i].p);24             sum += Bag[i].v;25         }26         memset(dp,0,sizeof(dp));27         dp[0] = 1;28         for(int i = 0; i < N; i++)   29         {30             for(int j = sum; j >= Bag[i].v; j--)31             {32                 dp[j] = max(dp[j],dp[j-Bag[i].v]*(1-Bag[i].p));33             }34         }35 36         for(int i = sum; i >= 0; i--)37         {38             if(dp[i] > 1-p)39             {40                 printf("%d\n",i);41                 break;42             }43         }44     }45     return 0;46 }