C/C++ 动态规划0-1背包问题

描述

你有一个背包，最多能容纳的重量是w。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和w，表示物品个数和背包重量。

接下来n行，每行两个数wi vi，表示第i个物品的重量和价值。输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

这两问的解法基本一样。第二问是在第一问解法延伸出来的，理解起来稍稍会复杂些。

第一问：

在这直接贴上第一问的代码，就不具体分析了。想看思路的，直接看第二问的解题思路即可。

int** DagDP(int n, int w, int* values, int* weights) {
    int** c = (int**)malloc(sizeof(int*) * (n + 1));
    for (size_t i = 0; i <= n; i++) {
        *(c + i) = (int*)malloc(sizeof(int) * (w + 1));
        ** (c + i) = 0;
    }
    for (size_t i = 1; i <= w; i++) {
        c[0][i] = 0;
    }
    for (size_t i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (weights[i - 1] <= j) {
                if (values[i - 1] + c[i - 1][j - weights[i - 1]] > c[i - 1][j]) {
                    c[i][j] = values[i - 1] + c[i - 1][j - weights[i - 1]];
                } else {
                    c[i][j] = c[i - 1][j];
                }
            } else {
                c[i][j] = c[i - 1][j];
            }
        }
    }
    return c;
}

解第二问的思路与第一问类似，依旧使用动态规划思想从小问题开始求解，最终得到最优解。每一个物品都会在不同的背包容量下尝试去装入，如果可以装入且装入后的价值大于装入前原背包价值那就更新。为了方便状态区分，我们认为第一行的1-w列的初始化值为-1，第一列（i=0）为0；（在第一问解法中第一行第一列都初始化为0，主要目的上方便用于运算。这是因为两者作用不一样，第一问初始化的0，可以当做价值为0的虚拟子问题的解，后续的问题可以很方便利用这个0解来更新。）

装入且装入后的价值大于装入前原背包价值的条件为(values[i-1] + dp2[i - 1][k - weights[i-1]]) > dp2[i][k]，（此处dp2[i][k]等于dp2[i-1][k]）。

如果想试着装入第i个物品。那么要先找到之前已经求得的小问题，找到小问题在加入第i个物品后背包的剩余容量的局部最优解。dp2[i - 1][k - weights[i-1]].（剩余容量指的是在当前背包容量的假设下加入第i个物品后的容量。过程反推的，加入这个物品后再去试着在小问题里面寻找能否再加入之前的其他物品）。如果寻得最优解即更新当前的解（dp2[i][k] = values[i-1] + dp2[i - 1][k - weights[i-1]];），否则继承小问题的解。

实际上，求解“恰好装满最大价值”跟求解“背包至多能装多大价值”的DP数组代码区别只是多了个dp2[i - 1][k - weights[i-1]] != -1 条件，因为第一个物品的问题的求解不需要依赖任何物品的问题，它就是最小子问题。多了个dp2[i - 1][k - weights[i-1]] != -1 条件 致使装入它的价值大于子问题解，当上一个子问题无解时候，这里也无解。
因为k - weights[i-1]位置处子问题无解，肯定说明包括它在内的以及它往前追溯的所有子问题都没一个能塞下进去。如果有解，那么在这条解路径上的第一个解一定是k - weights[i-1] = 0。
因此非-1的解一定是恰好装满。

整个过程图解：

假设背包最大容量为6时

解的组合关系：

代码：

    //若背包恰好装满，求至多能装多大价值的物品？
    int** dp2 = (int**)malloc(sizeof(int*) * (n + 1));
    for (size_t i = 0; i <= n; i++) {
        *(dp2 + i) = (int*)malloc(sizeof(int) * (w + 1));
        ** (dp2 + i) = 0;
    }
    for (size_t i = 1; i <= w; i++) {
        dp2[0][i] = 0;
    }
    // 值为 -1 表示从 0~i 的物品中没有体积刚好为 j 的物品，所以也就没有价值
      for (int k = 1; k <= w; k++) dp2[0][k] = -1;

      for (int i = 1; i <=n; i++)
      {
          for (int k = 1; k <= w; k++)
          {
              dp2[i][k] = dp2[i - 1][k];
              if (k - weights[i-1] >= 0 && dp2[i - 1][k - weights[i-1]] != -1)
                  //装入且装入后的价值大于装入前原背包价值 这里dp2[i-1][k] 与 dp2[i][k]等价，前面提前赋值了。
                  if ((values[i-1] + dp2[i - 1][k - weights[i-1]]) > dp2[i][k])
                  {
                      dp2[i][k] = values[i-1] + dp2[i - 1][k - weights[i-1]];
                  }
          }
      }
    printf("\n%d", (dp2[n][w] == -1 ? 0 : dp2[n][w]));

参考：

【dp】背包问题-阿里云开发者社区 (aliyun.com)