| 01背包和完全背包（可能是最易懂最详细的） | 您所在的位置：网站首页 › 详解种子和耕地问题的区别 › 01背包和完全背包（可能是最易懂最详细的） |
|
背包问题
01背包
什么是01背包
有n种物品，每种物品只有一个。每个物品有自己的重量和价值。有一个给定容量的背包，问这个背包最多能装的最大价值是多少。 动态规划三个基本步骤1.定义数组元素的含义 2.找出数组元素之间的关系式（递推式） 3.找出初始值。 下面以这三个基本步骤详细解释01背包的二维解法和一维解法。 例图： 重量价值物品0115物品1320物品2430………物品iw(weight)v(value) 二维解法（物品i的质量为w[i]，价值为v[i]） 首先定义一个二维数组dp[i][j]表示：在第0到i个物品中任取物品，放进容量为j的背包中，背包所能装的最大价值。 考虑dp[i][j]，相较于前一种情况，有放第i个物品和不放第i个物品两种情况。 当不放第i个物品时，那么情况很简单： dp[i][j]=dp[i-1][j]当放第i个物品时，前一种情况的背包容量就必须是j-w[i]，因为这样背包容量为j时才有足够的容量去装下第i个物品，那么递推公式写出来就是： dp[i][j]=dp[i-1][j-w[i]]+v[i]我们要求的是背包所能装的最大价值，那么就必须从这两种情况中取得所装价值最大的情况，即： dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])得出递推公式，接下来初始化dp数组。 下面这个表格，列代表背包容量，行代表物品i。大伙都知道二维数组dp初始化要填第一列和第一行，以例图为例： dp[i][j]01234物品0物品1物品2对于第一行，物品0的重量为1，即背包容量为1时才能放进去，所以容量为1之前的列全填0，容量为1及1后面的列全填物品0的价值。 dp[i][j]01234物品0015151515物品1物品2对于第一列，背包容量为0的时候什么也装不进去，所以全填0。 而其他位置因为是从上方和左上方推得，所以填什么都无所谓，为了方便我们全部初始化为0。 dp[i][j]01234物品0015151515物品100000物品200000至此数组初始化完成。 代码贴上 for(int i=1;i if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); //防止越界 else dp[i][j]=dp[i-1][j]; } } dp[i][j]01234物品0015151515物品1015152035物品2015152035所以0，1，2放入容量为4的背包的最大价值为35。 一维解法（滚动数组） 重量价值物品0115物品1320物品2430………物品iw(weight)v(value)在二维数组中，dp[i][j]总是从dp[i-1][…]也就是上一行推导出来，而此时除了i-1行的其他行都是没有用的，所以我们可以想到，只用一个一维数组，每次计算是把i-1行复制到当前行进行计算，这样可以优化空间复杂度。每次计算都更新这一行，看起来像是在滚动一样，所以也被称作滚动数组。 为了促进理解，我们还是拿例图举例。 dp[i][j]01234物品0015151515物品100000物品200000这是我们初始化后的二维数组，把物品0的数据复制到物品1中进行计算，即 dp[i][j]01234物品0015151515物品1015151515物品200000原本的递推公式 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])就可以转化为 dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])进一步优化为 dp[j]=max(dp[j],dp[j-w[i]]+v[i])因此，定义一个一维数组dp[j]，表示当前行背包容量为j时所装物品价值的最大值。 代码如下： for(int i=0;i if(j>=price[i]) //防止越界（当然可以不写，循环条件里写过了） dp[j]=max(dp[j],dp[j]-w[i]]+v[i]); } }很多人可能会疑惑，为什么背包容量要从后往前遍历呢？ 还是以上面的表格为例 dp[i][j]01234物品0015151515物品1015151515物品200000仅看物品1一行，由递推公式可知，每一个数据都是由当前这一列的数据和前面的数据取最大值得来。如果从前向后遍历，那么遍历到后面的时候，前面的数据已经发生改变，已经不是最初的数据了，也就是说同样的物品会放多次（注意这一点，对后面的完全背包有用）。而从后往前遍历，后面的数据改变后，遍历前面的时候因为用不到后面的数据，所以不会改变最初的数据。（讲的比较抽象，大家可以自己试试从前往后遍历） 例题：洛谷P1060 [NOIP2006 普及组] 开心的金明 可以用来试手 完全背包 什么是完全背包与01背包几乎相同，但是物品的数量是无限的。 解法同01背包，首先定义一个二维数组dp[i][j]表示：在第0到i个物品中任取物品，放进容量为j的背包中，背包所能装的最大价值。 考虑dp[i][j]，相较于前一种情况，有不放第i个物品和放k件第i个物品两种情况（k≥1) 与01背包相似，完全背包的递归方程如下 dp[i][j]=max{dp[i-1][j],max(dp[i-1][j-k*w[i]]+k*v[i])}(1≤k≤j/w[i])其中，里面的max是对于不同的k求max 这种方法没试过，根据我的理解应该是写一个三重循环遍历，复杂度贼高。 但是我们有个复杂度低的方法。大家注意01背包最后一点中所说，我们采用从后向前遍历背包容量的原因是从前向后遍历时同样的物品会被放多次，这不正好契合完全背包的题意吗？！ 我们把01背包一维数组做法的背包容量正过来遍历，直接就得到了完全背包的代码： for(int i=0;i if(j>=w[i]) //防止越界（当然可以不写，循环条件里写过了） dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } 完全填满的完全背包条件与完全背包相同，但要求求完全填满背包的同时求最大/小价值。 dp[0]赋0，若求最大价值其他值赋负无穷，若求最小其他值赋正无穷。以求最大价值为例（设所有物品价值均为1）。 01234重量为3的物品0-Inf-Inf-Inf-Inf只有容量为0的背包能被（空气）完全填满，价值为0，所以赋0。 其他数据赋负无穷，当进行下面的运算时，不能被填满的背包不取dp[j-w[i]]+v[i] 以上表为例，从左到右遍历，当背包容量为3时 dp[3]=max(dp[3],dp[3-3]+1)=1容量为0的背包正好能填满，容量为3的背包为容量为0的背包+重量为3的物品，所以可以把物品放入背包。 第二个物品重量为2 01234重量为2的物品0-Inf-Inf1-Inf当背包容量为3时， dp[3]=max(dp[3],dp[3-2]+1)=dp[3]=1背包容量为1的背包不能被填满，所以也不能通过填入重量为2的物品使背包容量为3的背包被填满，所以dp[3]不变。 完全填满例题：Codeforces 189 A. Cut Ribbon |
| CopyRight 2018-2019 实验室设备网 版权所有 |