大家好,又见面了,我是你们的朋友全栈君。
一、01背包问题
简述:n种物品,每种一个,选或不选随你,背包一定有容量,求不超过容量的情况下,价值最大。
递归方程:dp[i][v]=max{dp[i][v],dp[i-1][v-c[i]]+w[i]}
我们要注意的是下一次背包放I个物品的状态的可达性必然要满足上一次放I-1个物品时的可达性,觉得数学归纳法可以证明出来。所以这里有个隐含的判断,就是初始时memset(dp,0,sizeof(dp));在这里已经将dp清零,所以我们可以认为在dp==0是,这一节点是没有被访问到的。因为我们取得是大的值,自然0的情况怎么都不会被选中。
递推表示:
memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=m;j>=c[i];j--)//注意循环下标 dp[i][[j]=max(dp[i][j],dp[i-1][j-c[i]]+w[i]); //cout<<dp[n][m];//我们可以判断出:即使在m-1时已经装满,但是m最满足不能装更多东西的时候时,dp[n][m]是同值的
变式求值:
我们可以组合这几个关键字:恰好装满、装载量不限定、价值最大、价值最小
1、价值最小,装载量不限定
解释:第一种可能是来酱油的,哈哈,我们什么都不装不就可以了。但是,我想在这里说明一个问题,那就是容量是一个限制条件,而不是决定最优解的条件,不要本末倒置了。
2、价值最大,装载量不限定
3、价值最大,恰好装满
解释:参考《背包九讲》
我们需要处理的是它的初始化部分
#define INF -0x3f3f3f3f ........ memset(dp,INF,sizeof(dp)); dp[0]=0;
为什么要这样呢?开始我是不明白的。(现在还是不怎么理解,有木有!!!!)
看看大神的抽象解释:
为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。
4、价值最小,正好装满。
只需要把INF改成0x3f3f3f3f就可以了。
5、资源条件仅有一个。
举个例子来说。比如,给出一个数列 -1 19 0 34 -132 84 -2………
通过选取部分数字求和,使和尽量接近一个数N,或判断是否能正好加起来是N
这道题放到平时,可能惯性思维是暴力+剪枝,可是它是一个变相的背包问题,有木有!!!~~~~~
其实就是性价比为1(价值和体积之比为1)的情况。。。。。
6、价值形式改变
相关题目
1、hdu2546 饭卡(上述第5种情况)
Description
某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
Input
第一行为正整数n,表示菜的数量。n<=1000。
第二行包括n个正整数,表示每种菜的价格。价格不超过50。
第三行包括一个正整数m,表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
Sample Input
Sample Output
#include<iostream> #include<string.h> #define maxn 1000+5 using namespace std; int dp[maxn]; int w[maxn]; int main(){ int n; while(cin>>n && n){ int max1=0,p=0; for(int i=1;i<=n;i++){ cin>>w[i]; if(max1<w[i]){ max1=w[i];//价格最大的物品放在最后选择一定是最优的 p=i; } } int m; cin>>m; memset(dp,0,sizeof(dp)); dp[0]=1;//表示什么都不买的状态是可达的 if (m<5) cout<<m<<endl; else{ m=m-5; w[p]=m+1;//小技巧,使得怎么都不能选到这个物品 for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ if(dp[j-w[i]])dp[j]=1;//表示此状态可达 } } int ma=0; for(int i=m;i>=0;i--){ if(dp[i]) {ma=i;break;} } cout<<((m-ma)+(5-max1))<<endl; } } return 0; }
2、hdu2602 Bone Collector(情况2)
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
31).
#include<iostream> #include<string.h> #define maxn 1000+5 using namespace std; long long dp[maxn]; int v[maxn]; int w[maxn]; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n; cin>>m; for(int i=1;i<=n;i++){ cin>>v[i]; } for(int i=1;i<=n;i++){ cin>>w[i]; } memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[m]<<endl; } return 0; }
3、hdu2955(情况2)
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.
#include<iostream> #include<string.h> #define maxn 10000+5 #define esp 0.0000001 using namespace std; double dp[maxn]; double p[100+5]; int c[100+5]; int main(){ int t; cin>>t; while(t--){ int n; double mp; cin>>mp>>n; mp=1-mp; int mc=0; for(int i=1;i<=n;i++){ cin>>c[i]>>p[i]; mc=mc+c[i]; p[i]=1-p[i]; } memset(dp,0,sizeof(dp)); dp[0]=1;//什么都没有偷,逃跑概率是1 for(int i=1;i<=n;i++){ for(int j=mc;j>=c[i];j--) if (dp[j-c[i]]>0){//表示这种状态是可达的 dp[j]=max(dp[j],dp[j-c[i]]*p[i]);//偷盗当前数量的钱后,最优的解肯定是逃跑概率最小的时候 } } int i; for(i=mc;i>=0;i--){ if(dp[i]-mp>esp) break;//只要逃跑概率大于mp,那么这些状态都是可达的。 } cout<<i<<endl; } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155073.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...