首页 > 代码库 > HDU 2955 Robberies(0-1背包)
HDU 2955 Robberies(0-1背包)
http://acm.hdu.edu.cn/showproblem.php?pid=2955
题意:一个抢劫犯要去抢劫银行,给出了几家银行的资金和被抓概率,要求在被抓概率不大于给出的被抓概率的情况下,计算出所能抢劫得到的最多资金。
思路:一开始把被抓概率当做背包容量来做,结果错了,很重要的一点就是逃脱概率的计算,不是简单的相加相减,而是在上一家银行抢劫时的逃脱概率再乘以这一次的逃脱概率。
举个例子:
三家银行的被抓概率为P1,P2,P3。那么去抢劫这三家银行的逃脱概率为(1-P1)*(1-P2)*(1-P3)。
我们把银行的资金作为背包容量,状态转移方程为dp[j] = max(dp[j] , dp[j-m[i]] * (1-p[i])),dp[j]表示在抢劫了j资金之后的最大逃脱概率。
最后我们只需要逆序遍历dp数组,一旦它的逃脱概率大于了给定的逃脱概率,那么此时的i值就是所能得到的最大资金。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 5000+5; 7 8 int n; 9 double dp[maxn];10 double p;11 double pi[maxn];12 int sum;13 int num[maxn];14 15 16 17 int main()18 {19 //freopen("D:\\txt.txt", "r", stdin);20 int t;21 cin >> t;22 while (t--)23 {24 memset(dp, 0, sizeof(dp));25 cin >> p >> n;26 sum = 0;27 for (int i = 1; i <= n; i++)28 {29 cin >> num[i] >> pi[i];30 sum += num[i];31 }32 dp[0] = 1; //没抢时逃脱概率为1,这个不能漏33 for (int i = 1; i <= n; i++)34 {35 for (int j = sum; j >= num[i]; j--)36 dp[j] = max(dp[j], dp[j - num[i]] * (1 - pi[i]));37 }38 for (int i = sum; i >= 0; i--)39 {40 if (dp[i] > (1 - p))41 {42 cout << i << endl;43 break;44 }45 }46 }47 return 0;48 }
HDU 2955 Robberies(0-1背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。