HDU-2955-Robberies(0-1背包)
2020-03-30 08:01:44来源:博客园 阅读 ()
HDU-2955-Robberies(0-1背包)
Robberies
题意:题目的大概意思是说一个人想去强银行,但他又怕被抓,但他通过观察计算出了在每个银行被抓的概率,最后他提出如果他能承受最大被抓的概率,现在他想知道,在他能忍受的情况下,他能抢得的最大金额。
题解:这一题属于0-1背包的变种题,它与那些常规的题目的不同之处主要体现在如下方面:
(1)在普通的0-1背包问题中只要确定了:volume与value变量,下面就比较方便做了,但这一题有点改变,我们应该用每个银行打算抢多少钱的总数你来做volume变量。
(2)通常的0-1背包问题需要我们直接求题目问我们的最大值,而在这里需要我们从另外一个方面来求它的最大值
(3)一般的0-1背包问题中dp数组中一般存贮的是我们要求的属性值,这一题我们要求的属性值是他能抢到的最大金额,而在这里如果这样做的话,可能会比较麻烦,所以这里使用它来存储在抢到j的时候的逃脱概率,是一个double类型的值。
(4)最后遍历输出的时候,当(1-dp[i]<=P)的时候,表示他在能承受的范围内,能抢到的最大金额为i,遍历整个数组,取最大值即可。
代码:
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int main(){ 6 int T; 7 double P; 8 int N; 9 cin>>T; 10 while(T--){ 11 scanf("%lf%d",&P,&N); 12 int M[20000]={0}; 13 double Pj[20000]={0}; 14 int sum=0; 15 for(int i=1;i<=N;i++){ 16 scanf("%d %lf",&M[i],&Pj[i]); 17 sum=sum+M[i]; 18 }//数据输入完毕 19 double dp[200000]={0}; 20 dp[0]=1;//抢了 0 万元 成功逃跑的概率为 1 21 for(int i=1;i<=N;i++){ 22 for(int j=sum;j>=M[i];j--){ 23 dp[j]=max(dp[j],dp[j-M[i]]*(1-Pj[i])); 24 } 25 } 26 int ans=0; 27 for(int i=sum;i>=0;i--){ 28 if(1-dp[i]<=P){ 29 ans=max(ans,i); 30 break; 31 } 32 } 33 cout<<ans<<endl; 34 } 35 return 0; 36 }
原文链接:https://www.cnblogs.com/blogxsc/p/12596193.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:软件工程第三次作业
下一篇:DSA_07:递归算法
- 多重背包问题 2019-11-04
- NOIP模拟day1-T1(完全背包) 2019-10-12
- 背包问题 2019-10-08
- IEEE浮点表示 (原发布 csdn 2018-10-14 10:29:33) 2019-09-08
- 多重背包模板 2019-01-21
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash