01背包 完全背包

嗨害嗨,作业来喽

公司主营业务:做网站、成都网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出莒南免费做网站回馈大家。

背包问题

01背包和完全背包问题都是一个背景下的:我有一个容量为M的背包,现在地上有N个物品,我跟个小偷似的眼里只有i个物品的价值vi和重量wi,现在我要做的就是为了偷的东西更值钱拿走一些东西,使它们的价值是所有方案里最大的

01背包

背景如上,01背包就是我眼前的这些东西都是孤品,只有一件,求最大价值。

那么有些人会先想到:我可不可以等他们输入时先计算出他们的性价比,然后再去给他们的性价比排序,得出答案呢?这就是用贪心的思想去想这道问题了,但显然不行,因为你无法把空间利用到最大。不用贪心,我们用什么?答案就是——动态规划

我们可以把问题看成这样:用一个二维数组c[N][M]来表示N个物品放入M容量的背包中的最大价值,那么要计算最大价值,每个物品就只有两种选择方式

1.不拿,直接照抄c[i-1][j]

2.拿,拿的话我们首先要把j-w[i]把物品放进去,然后再把c[i][j-w[i]]中加上i物品的价值v[i],即得:c[i][j-w[i]]+v[i]

也就是说,我们把每个物品都拆成这样的选最优的问题,就可以得到一行很简单的式子:max(c[i-1][j],c[i][j-w[i]]+v[i]);这就是状态转移方程式

那么有了这个我们就可以写代码了,但是注意初始化c[0][j]=0,c[i][0]=0:

1 for(int i=1;i<=n;i++){
2         for(int j=1;j<=m;j++){
3             if(j>=w[i]) c[i][j]=max(c[i-1][j],c[i][j-w[i]]+v[i]);
4             else c[i][j]=c[i-1][j];
5         }
6     } 
7     cout<            
            
                            
文章题目:01背包 完全背包
转载来源:http://scyanting.com/article/dsoipgs.html