背包问题

Posted on:2024年8月10日 at 17:06

有 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，那么我们可以用滚动数组，逆序遍历的方式进行空间优化。

 function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        if(j < weights[0]){ //如果容量不能放下物品0的重量，那么价值为0
           f[0][j] = 0
        }else{ //否则等于物体0的价值
           f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])
            }
        }
    }
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)

合并循环

现在方法里面有两个大循环，它们可以合并成一个。

function knapsack(weights, values, W) {
  var n = weights.length;
  var f = new Array(n);
  for (var i = 0; i < n; i++) {
    f[i] = [];
  }
  for (var i = 0; i < n; i++) {
    for (var j = 0; j <= W; j++) {
      if (i === 0) {
        //第一行
        f[i][j] = j < weights[i] ? 0 : values[i];
      } else {
        if (j < weights[i]) {
          //等于之前的最优值
          f[i][j] = f[i - 1][j];
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]);
        }
      }
    }
  }
  return f[n - 1][W];
}

然后我们再认真地思考一下，为什么要孤零零地专门处理第一行呢？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}$的情况，方程与其他教科书的一模一样了！

function knapsack(weights, values, W) {
  var n = weights.length;
  var f = new Array(n);
  f[-1] = new Array(W + 1).fill(0);
  for (var i = 0; i < n; i++) {
    //注意边界，没有等号
    f[i] = new Array(W).fill(0);
    for (var j = 0; j <= W; j++) {
      //注意边界，有等号
      if (j < weights[i]) {
        //注意边界， 没有等号
        f[i][j] = f[i - 1][j];
      } else {
        f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]); //case 3
      }
    }
  }
  return f[n - 1][W];
}

选择物品

上面讲解了如何求得最大价值，现在我们看到底选择了哪些物品，这个在现实中更有意义。许多书与博客很少提到这一点，就算给出的代码也不对，估计是在设计状态矩阵就出错了。

仔细观察矩阵，从${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就行了。

function knapsack(weights, values, W) {
  var n = weights.length;
  var f = new Array(n);
  f[-1] = new Array(W + 1).fill(0);
  var selected = [];
  for (var i = 0; i < n; i++) {
    //注意边界，没有等号
    f[i] = []; //创建当前的二维数组
    for (var j = 0; j <= W; j++) {
      //注意边界，有等号
      if (j < weights[i]) {
        //注意边界， 没有等号
        f[i][j] = f[i - 1][j]; //case 1
      } else {
        f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]); //case 2
      }
    }
  }
  var j = W,
    w = 0;
  for (var i = n - 1; i >= 0; i--) {
    if (f[i][j] > f[i - 1][j]) {
      selected.push(i);
      console.log("物品", i, "其重量为", weights[i], "其价格为", values[i]);
      j = j - weights[i];
      w += weights[i];
    }
  }
  console.log("背包最大承重为", W, " 现在重量为", w, " 总价值为", f[n - 1][W]);
  return [f[n - 1][W], selected.reverse()];
}
var a = knapsack([2, 3, 4, 1], [2, 5, 3, 2], 5);
console.log(a);
var b = knapsack([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10);
console.log(b);

使用滚动数组压缩空间

所谓滚动数组，目的在于优化空间，因为目前我们是使用一个${ij}$的二维数组来储存每一步的最优解。在求解的过程中，我们可以发现，当前状态只与前一行的状态有关，那么更之前存储的状态信息已经无用了，可以舍弃的，我们只需要存储当前状态和前一行状态，所以只需使用${2j}$的空间，循环滚动使用，就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。

function knapsack(weights, values, W) {
  var n = weights.length;
  var lineA = new Array(W + 1).fill(0);
  var lineB = [],
    lastLine = 0,
    currLine;
  var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
  for (var i = 0; i < n; i++) {
    currLine = lastLine === 0 ? 1 : 0; //决定当前要覆写滚动数组的哪一行
    for (var j = 0; j <= W; j++) {
      f[currLine][j] = f[lastLine][j]; //case2 等于另一行的同一列的值
      if (j >= weights[i]) {
        var a = f[lastLine][j];
        var b = f[lastLine][j - weights[i]] + values[i];
        f[currLine][j] = Math.max(a, b); //case3
      }
    }
    lastLine = currLine; //交换行
  }
  return f[currLine][W];
}

var a = knapsack([2, 3, 4, 1], [2, 5, 3, 2], 5);
console.log(a);
var b = knapsack([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10);
console.log(b);

注意，这种解法由于丢弃了之前N行的数据，因此很难解出挑选的物品，只能求最大价值。

递归法解01背包

function knapsack(n, W, weights, values, selected) {
  if (n == 0 || W == 0) {
    //当物品数量为0，或者背包容量为0时，最优解为0
    return 0;
  } else {
    //从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
    for (var i = n - 1; i >= 0; i--) {
      //如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
      //在这种情况的最优解为f(n-1,C)
      if (weights[i] > W) {
        return knapsack(n - 1, W, weights, values, selected);
      } else {
        var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
        var b =
          values[i] +
          knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
        //返回选择物品i和不选择物品i中最优解大的一个
        if (a > b) {
          selected[i] = 0; //这种情况下表示物品i未被选取
          return a;
        } else {
          selected[i] = 1; //物品i被选取
          return b;
        }
      }
    }
  }
}
var selected = [],
  ws = [2, 2, 6, 5, 4],
  vs = [6, 3, 5, 4, 6];
var b = knapsack(5, 10, ws, vs, selected);
console.log(b); //15
selected.forEach(function (el, i) {
  if (el) {
    console.log("选择了物品" + i + " 其重量为" + ws[i] + " 其价值为" + vs[i]);
  }
});
原文转自：https://fe.ecool.fun/topic/d7bda93c-f848-4818-a1b5-31a063ab15f7