【题目链接】：click here~~
代码：
/** Problem: HDU No.2955* Running time: 46MS* Complier: G++* Author: ACM_herongwei* Create Time: 15:01 2015/9/9 星期三* zeroonebags* 用成功逃走的概率当做价值！银行的总钱数当做背包容量！单个银行的钱数体积，然后zeronebags*/#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#define CLR(c,v) (memset(c,v,sizeof(c)))using namespace std;template <typename _T>inline _T Max(_T a,_T b){return (a>b)?(a):(b);}template <typename _T>inline _T Maxx(_T a,_T b,_T c){return (a>Max(b,c))?(a):(Max(b,c));}const int N = 1e4+ 10;double dp[N];int volume[N];double p_value[N];int main(){int Ncase;scanf("%d",&Ncase);while(Ncase–){CLR(dp,0);CLR(volume,0);CLR(p_value,0);double P;int n_banks;int sum_v=0;scanf("%lf %d",&P,&n_banks);P=1.0-P;// 逃走的概率for(int i=0; i<n_banks; ++i) // max:1000{scanf("%d %lf",&volume[i],&p_value[i]);p_value[i]=1.0-p_value[i]; //逃走概率=1-每家银行被抓概率sum_v+=volume[i];}dp[0]=1;// !!!一分钱没抢，再也不担心被警察抓for(int i=0; i<n_banks; ++i){for(int j=sum_v; j>=volume[i]; –j){if(dp[j]<=dp[j-volume[i]]*p_value[i]) //注意是相乘！{dp[j]=dp[j-volume[i]]*p_value[i];}}}int i;for(i=sum_v; i>=0; –i) //从总价值往前计算，判断相应的概率{if(dp[i]>=P){break;}}printf("%d\n",i);}return 0;}/*sample input30.04 31 0.022 0.033 0.050.06 32 0.032 0.033 0.050.10 31 0.032 0.023 0.05sample ouput246*/
版权声明：本文为博主原创文章，，未经博主允许不得转载。
如果你不出去走走，你就会以为这就是世界。
