欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HDU-2955-Robberies(0-1背包)

程序员文章站 2022-06-15 12:45:13
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 }