邹易明,销量最高的手机,何哲旗
题意：题目的大概意思是说一个人想去强银行，但他又怕被抓，但他通过观察计算出了在每个银行被抓的概率，最后他提出如果他能承受最大被抓的概率，现在他想知道，在他能忍受的情况下，他能抢得的最大金额。
题解：这一题属于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 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论