HDU 2955 Robberies （转化概率-01背包）

本文主要是介绍HDU 2955 Robberies （转化概率-01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】：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 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 ouput
2
4
6
*/

这篇关于HDU 2955 Robberies （转化概率-01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---