01背包与完全背包讲解.ppt

ACM寒假集训--01背包与完全背包**话题引入:小P同学爱好探险寻宝,一天他去了伊利哇呀半岛发现了一批宝藏,但不幸的是小P很懒,出门只带了一个背包,所以注定他不能带走所有的宝藏。但是小P又很贪心想带走尽量多的宝藏。。。已知每种宝贝的重量与价值是不一样的,小P很笨,没有你聪明,但是聪明的你想到了好的解决方案了吗?**数据分析:假设背包的容量上限为5kgA宝贝重2kg价值3,000,000,000$B宝贝重3kg价值4,000,000,000$C宝贝重4KG价值6,500,000,000$D宝贝重5KG价值6,700,000,000$E宝贝重6KG价值10,000,000,000$你认为怎么装才最合理为什么啊?解题思路?你是怎么想的啊???**思考贪心和01背包的区别一般同学们会考录到用贪心的算法通过求最大的性价比来填满背包,大家考录一下这样会有什么样的不妥之处。。。。贪心与背包的不同:首先说一下贪心是每一步都是最优的决策,就是每次方我都会放进去解决问题的目前最好的结果。贪心虽然会带来每一次最优但是不一定是整体最优。(比如说C的性价比最高,但是放了C就不能放别的了,总价值就不如放A和B的多了)背包可以从宏观上整体得到一个最优的结果。**01背包原理阐述01背包的原理其实不是很难理解,你不要被他唬住,不要畏惧,其实他也就是那么一回事。。。。问题的特点是:每种物品一件,可以选择放1或不放0。用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v-p[i]]+w[i],f[i-1][v]}在这里解释一下公式中‘,’号前面是放的状态,后面是不放的状态;如果在这里第i件物品放的话就表明它是由第i-1的状态传递过来的并且加上新的价值w[i],如果不放就表明这里是保持第i-1的状态没有增加新的价值。博客链接:http://blog./s/**题目举例:HDU2602思考一下应该怎么解决?**你看懂了吗。。?**代码研讨#include<>#defineMAXN1002intdp[MAXN][MAXN],w[MAXN],p[MAXN];int_max(inta,intb){returna>b?a:b;}intmain(){intn,v,T,i,j;scanf("%d",&T);while(T--){scanf("%d%d",&n,&v);for(i=1;i<=n;i++){scanf("%d",&w[i]);}for(i=1;i<=n;i++){scanf("%d",&p[i]);}for(i=0;i<=n;i++)dp[i][0]=0;for(i=0;i<=v;i++)dp[0][i]=0;for(i=1;i<=n;i++){for(j=0;j<=v;j++){dp[i][j]=dp[i-1][j];if(j>=p[i])dp[i][j]=_max(dp[i-1][j],dp[i-1][j-p[i]]+w[i]);}}printf("%d\n",dp[n][v]);}return0;}一维数组的优化#include<>#include<>#defineMAXN1002intmax_num(inta,intb){returna>b?a:b;}intdp[MAXN],w[MAXN],p[MAXN];intmain(){intn,v,T,i,j;scanf("%d",&T);while(T--){scanf("%d%d",&n,&v);for(i=1;i<=n;i++){scanf("%d",&w[i]);}for(i=1;i<=n;i++){scanf("%d",&p[i]);}**for(i=0;i<=v;i++){dp[i]=0;}for(i=1;i<=n;i++){for(j=v;j>=0;j--){if(j>=p[i])dp[j]=max_num(dp[j],dp[j-p[i]]+w[i]);}}printf("%d\n",dp[v]);}return0;}