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://cxhlcq.com/article/dsoipgs.html