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

描述

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

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

输入描述：

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

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

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

第一问很常见，就不整理了。直接看第二问。

解第二问的思路与第一问类似，依旧使用动态规划思想从小问题开始求解，最终得到最优解。每一个物品都会在不同的背包容量下尝试去装入，如果可以装入且装入后的价值大于装入前原背包价值那就更新。为了方便状态区分，我们认为第一行的1-w列的初始化值为-1，第一列（i=0）为0；

装入且装入后的价值大于装入前原背包价值的条件为(values[i-1] + dp2[i - 1][k - weights[i-1]]) > dp2[i][k]。除此之外还需设定一个前提条件dp2[i - 1][k - weights[i-1]] != -1。因为第一个物品的问题的求解不需要依赖任何物品的问题，它就是最小子问题。（在记忆数组中只需在背包容量为weights[i-1]时更新为对应的价值，其余位置全为-1。）

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