01背包问题

题目

有一个背包的容积为\(m\)，有\(n\)个物品，每个物品的体积为\(w\)，权重为\(v\)，每个物品只能取\(1\)次放入背包中，背包所有物品权重和最大是多少？

求值

创建一个状态矩阵\(dp\)，横坐标\(i\)表示物品编号，纵坐标\(j\)表示背包容量。\(dp[i][j]\)表示在已用背包容量为\(j\)的情况下，考虑第\(i\)件物品装不装时，背包的最大总价值，可知状态矩阵\(dp\)第0行和第0列都为0。
对于第\(i\)个物品，在已用背包容量为\(j\)时来说，物品只有放入背包和不放入背包两种情况，两者取其中的最大值作为\(dp[i][j]\)的值。若放入背包，当前最大权重等于考虑上一个物品放不放入背包时，当前背包已用容量减去这个物品所占的体积之后的背包容量的最大权重加上当前物品的权重；若不放入背包，当前最大权重等于考虑上一个物品放不放入背包时，当前已用背包容量的最大权重；取两者最大值作为\(dp[i][j]\)的值，即\(dp[i][j] = max(dp[i - 1][j - w[i] + v[i], dp[i - 1][j]])\)，这称为01背包的状态迁移方程，也是解决本文所有背包问题的关键。将状态矩阵\(dp\)填充完毕之后，\(dp[n][m]\)就是背包的最大权重。算法实现如下：

for (int i = 1; i <= n; i++){
  for (int j = 1; j <= m; j++){
    if (j >= w[i]){
      dp[i][j] = mnax(dp[i - 1][j - w[i]] + v[i]);
    }
    else {
      dp[i][j] = dp[i - 1][j];
    }
  }
}

回溯

如何求出到底是哪些物品装入，哪些物品没装入呢？设\(m=8，n=4，w={2,3,4,5}，v={3,4,5,8}\)，可画出其状态矩阵\(dp\)：

从\(dp[4][8]\)开始回溯，根据状态迁移方程\(dp[i][j] = max(dp[i - 1][j - w[i] + v[i], dp[i - 1][j]])\)可知，若\(dp[i][j]\not=dp[i-1][j]\)，则第\(i\)件物品一定被放入背包，若\(dp[i][j]=dp[i-1][j]\)，则至少有一种情况物品\(i\)没被放入背包。由于\(dp[4][8]\not=dp[3][8]\)，所以第\(4\)件物品被放入背包，现在问题就变成了已知背包容量为\(8-5=3\)，物品数量为\(4-1=3\)最大权重为\(12-8=4\)，求哪些物品被装入背包。根据状态迁移方程，状态回溯到\(dp[i-1][j-w[i]]\)，即\(dp[3][3]\)，而$dp[3][3]=dp[2][3]，所以人为第\(3\)件物品没有放进背包；状态回溯到\(dp[2][3]\)，\(dp[2][3]\not=dp[1][3]\)，所以第\(2\)件物品被放入背包；状态回溯到\(dp[1][0]\)，此时已不必再回溯，因为剩余的背包容量为\(0\)。得出答案，物品\(4，2\)被放入背包。算法实现如下：

int i = n, j = m;
int lis[n] = {0};
while (j != 0) {
  if (dp[i][j] == dp[i-1][j]) {
    i = i - 1;
  } 
  else {
  lis[i]++;
  j = j - w[i];
  i = i - 1;
  }
}

其中，数组\(lis\)表示物品装填情况，1为放入，0为不放入。

完全背包问题

题目

有一个背包的容积为\(m\)，有\(n\)个物品，每个物品的体积为\(w\)，权重为\(v\)，每个物品可以取无限次放入背包中，背包所有物品权重和最大是多少？

求解

完全背包问题和01背包问题唯一的区别就是后者的每一种物品只能取1次，而前者的每一种物品可以取无限次。01背包状态迁移方程为\(dp[i][j] = max(dp[i - 1][j - w[i] + v[i], dp[i - 1][j]])\)，若设\(k\)为一种物品被放入背包中的次数，则可以得到完全背包问题的状态迁移方程\(dp[i][j] = max(dp[i - 1][j - k * w[i] + k * v[i], dp[i - 1][j]])\)，当\(k\)可以为0时，状态迁移方程可以简化为\(dp[i][j] = max(dp[i - 1][j - k * w[i] + k * v[i])(k=0,1,2,3,4···)\)。算法实现如下：

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    if (j >= w[i]) {
      for (int k = 0; k * v[i] <= j; k++) {
        dp[i][j] = max(dp[i - 1][j - k * w] + k * w[i], dp[i][j])
      }
    }
    else {
      dp[i][j] = dp[i - 1][j];
    }
  }
}

回溯

沿用上次的例子懒得想新数据，设\(m=8，n=4，w={2,3,4,5}，v={3,4,5,8}\)，可画出其状态矩阵\(dp\)：

从\(dp[4][8]\)开始回溯，根据状态迁移方程\(dp[i][j] = max(dp[i - 1][j - k * w[i] + k * v[i])(k=0,1,2,3,4···)\)可知，若\(dp[i][j]\not=dp[i-1][i]\)，则第\(i\)件物品一定被放入背包，若\(dp[i][j]=dp[i-1][j]\)，则至少有一种情况物品\(i\)没被放入背包，即\(k=0\)。由于\(dp[4][8]\)=dp[3][8]，所以认为第\(4\)件物品没被放入背包；状态回溯到\(dp[3][8]\)，由于\(dp[3][8]\)=dp[2][8]，所以认为第\(3\)件物品没被放入背包；状态回溯到\(dp[2][8]\)，由于\(dp[2][8]\)=dp[1][8]，所以认为第\(2\)件物品没被放入背包；状态回溯到\(dp[1][8]\)，由于\(dp[1][8]\notdp[0][8]\)，所以物品1至少有1件被放入背包；状态回溯到\(dp[1][6]\)，由于由于\(dp[1][6]\notdp[0][6]\)，所以物品1又有1件被放入背包；状态回溯到\(dp[1][4]\)，由于\(dp[1][4]\notdp[0][4]\)，所以物品1又有1件被放入背包；状态回溯到\(dp[1][2]\)，由于\(dp[1][2]\notdp[0][2]\)，所以物品1又有1件被放入背包；状态回溯到\(dp[1][0]\)，此时停止回溯，因为剩余的背包容量为0。得出答案，物品1被放入4次。算法实现如下：

int i = n, j = m;
int lis[n] = {0};
while (j != 0) {
  if (dp[i][j] == dp[i - 1][j]) {
    i = i - 1;
  }
  else {
    lis[i]++;
    j = j - w[i];
  }
}

其中数组\(lis\)中的数字表示物品被装入的次数。