问答题【789/1593】背包问题
有 N 件物品和一个容量是 V 的背包。每件物品有且只有一件。
第 i 件物品的体积是 v[i] ，价值是 w[i] 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
示例 1：
输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。
示例 2：
输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
参考答案：
这是最为基础的背包问题，每种物品只有一件，可以选择取或者不取。
问题描述可以归结为：将N种物品有选择地放入容量为V的背包中，要求背包中的物品价值最大。
尝试提炼其子问题：将i种物品有选择地放入容量为V的背包中，要求背包中的物品价值最大。
那么由子问题转移到父问题的方程为：
f(i,V) = max{f(i-1,V), f(i-1,V-v[i]) + w[i]}
解释如下：“将前i件物品放入容量为V的背包中”这个子问题，若只考虑第i件物品的策略（放或者不放），那么就可以转化为一个只关系到前i-1件物品的问题。
- 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；
- 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为V-v[i]的背包中”，此时能获得的最大价值就是f(i-1, V-v[i])再加上通过放入第i件物品获得的价值w[i]。
时间复杂度已经无法优化，我们可以尝试优化空间复杂度。
观察状态转移方程，发现当前状态i只和前一个状态有关i-1，那么我们可以用滚动数组，逆序遍历的方式进行空间优化。
1 function knapsack(weights, values, W){ 2 var n = weights.length -1 3 var f = [[]] 4 for(var j = 0; j <= W; j++){ 5 if(j < weights[0]){ //如果容量不能放下物品0的重量，那么价值为0 6 f[0][j] = 0 7 }else{ //否则等于物体0的价值 8 f[0][j] = values[0] 9 } 10 } 11 for(var j = 0; j <= W; j++){ 12 for(var i = 1; i <= n; i++ ){ 13 if(!f[i]){ //创建新一行 14 f[i] = [] 15 } 16 if(j < weights[i]){ //等于之前的最优值 17 f[i][j] = f[i-1][j] 18 }else{ 19 f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 20 } 21 } 22 } 23 return f[n][W] 24} 25var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10) 26console.log(a)
合并循环
现在方法里面有两个大循环，它们可以合并成一个。
1function knapsack(weights, values, W){ 2 var n = weights.length; 3 var f = new Array(n) 4 for(var i = 0 ; i < n; i++){ 5 f[i] = [] 6 } 7 for(var i = 0; i < n; i++ ){ 8 for(var j = 0; j <= W; j++){ 9 if(i === 0){ //第一行 10 f[i][j] = j < weights[i] ? 0 : values[i] 11 }else{ 12 if(j < weights[i]){ //等于之前的最优值 13 f[i][j] = f[i-1][j] 14 }else{ 15 f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 16 } 17 } 18 } 19 } 20 return f[n-1][W] 21}
然后我们再认真地思考一下，为什么要孤零零地专门处理第一行呢？f[i][j] = j < weights[i] ? 0 : values[i]是不是能适用于下面这一行f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 。Math.max可以轻松转换为三元表达式，结构极其相似。而看一下i-1的边界问题，有的书与博客为了解决它，会添加第0行，全部都是0，然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0>0}$的情况，方程与其他教科书的一模一样了！
1function knapsack(weights, values, W){ 2 var n = weights.length; 3 var f = new Array(n) 4 f[-1] = new Array(W+1).fill(0) 5 for(var i = 0 ; i < n ; i++){ //注意边界，没有等号 6 f[i] = new Array(W).fill(0) 7 for(var j=0; j<=W; j++){//注意边界，有等号 8 if( j < weights[i] ){ //注意边界， 没有等号 9 f[i][j] = f[i-1][j] 10 }else{ 11 f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3 12 } 13 } 14 } 15 return f[n-1][W] 16}
选择物品
上面讲解了如何求得最大价值，现在我们看到底选择了哪些物品，这个在现实中更有意义。许多书与博客很少提到这一点，就算给出的代码也不对，估计是在设计状态矩阵就出错了。
仔细观察矩阵，从${f(n-1,W)}$逆着走向${f(0,0)}$，设i=n-1,j=W，如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品，因此我们只要当前行不等于上一行的总价值，就能挑出第i件物品，然后j减去该物品的重量，一直找到j = 0就行了。
1function knapsack(weights, values, W){ 2 var n = weights.length; 3 var f = new Array(n) 4 f[-1] = new Array(W+1).fill(0) 5 var selected = []; 6 for(var i = 0 ; i < n ; i++){ //注意边界，没有等号 7 f[i] = [] //创建当前的二维数组 8 for(var j=0; j<=W; j++){ //注意边界，有等号 9 if( j < weights[i] ){ //注意边界， 没有等号 10 f[i][j] = f[i-1][j]//case 1 11 }else{ 12 f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2 13 } 14 } 15 } 16 var j = W, w = 0 17 for(var i=n-1; i>=0; i--){ 18 if(f[i][j] > f[i-1][j]){ 19 selected.push(i) 20 console.log("物品",i,"其重量为", weights[i],"其价格为", values[i]) 21 j = j - weights[i]; 22 w += weights[i] 23 } 24 } 25 console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W]) 26 return [f[n-1][W], selected.reverse() ] 27} 28var a = knapsack([2,3,4,1],[2,5,3, 2],5) 29console.log(a) 30var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10) 31console.log(b)
使用滚动数组压缩空间
所谓滚动数组，目的在于优化空间，因为目前我们是使用一个${ij}$的二维数组来储存每一步的最优解。在求解的过程中，我们可以发现，当前状态只与前一行的状态有关，那么更之前存储的状态信息已经无用了，可以舍弃的，我们只需要存储当前状态和前一行状态，所以只需使用${2j}$的空间，循环滚动使用，就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。
1function knapsack(weights, values, W){ 2 var n = weights.length 3 var lineA = new Array(W+1).fill(0) 4 var lineB = [], lastLine = 0, currLine 5 var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行 6 for(var i = 0; i < n; i++){ 7 currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行 8 for(var j=0; j<=W; j++){ 9 f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值 10 if( j>= weights[i] ){ 11 var a = f[lastLine][j] 12 var b = f[lastLine][j-weights[i]] + values[i] 13 f[currLine][j] = Math.max(a, b);//case3 14 } 15 16 } 17 lastLine = currLine//交换行 18 } 19 return f[currLine][W]; 20} 21 22var a = knapsack([2,3,4,1],[2,5,3, 2],5) 23console.log(a) 24var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10) 25console.log(b)
注意，这种解法由于丢弃了之前N行的数据，因此很难解出挑选的物品，只能求最大价值。
递归法解01背包
1function knapsack(n, W, weights, values, selected) { 2 if (n == 0 || W == 0) { 3 //当物品数量为0，或者背包容量为0时，最优解为0 4 return 0; 5 } else { 6 //从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中 7 for (var i = n - 1; i >= 0; i--) { 8 //如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品 9 //在这种情况的最优解为f(n-1,C) 10 if (weights[i] > W) { 11 return knapsack(n - 1, W, weights, values, selected); 12 } else { 13 var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解 14 var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解 15 //返回选择物品i和不选择物品i中最优解大的一个 16 if (a > b) { 17 selected[i] = 0; //这种情况下表示物品i未被选取 18 return a; 19 } else { 20 selected[i] = 1; //物品i被选取 21 return b; 22 } 23 } 24 } 25 } 26} 27var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6] 28var b = knapsack( 5, 10, ws, vs, selected) 29console.log(b) //15 30selected.forEach(function(el,i){ 31 if(el){ 32 console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i]) 33 } 34})
最近更新时间：2024-08-10
