如果问题是一系列物品的选或不选，则都可以归纳为背包问题

01背包：416. 分割等和子集474. 一和零494. 目标和
完全背包：1449. 数位成本和为目标值的最大数字322. 零钱兑换518. 零钱兑换 II279. 完全平方数

动态规划原理

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间。
所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

• 最优性原理

最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。
[

](https://blog.csdn.net/qq_38410730/article/details/81667885)

Ⅰ 01背包问题

1 问题描述

有件物品和一个容量为的背包。第i件物品的重量是，价值是，求将哪些物品装入背包可使物品总重量不超过背包容量的情况下价值总和最大。

2 基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

首先定义表示当前背包容量为 j ，前 i 个物品的最佳组合所对应的价值。那么对于N件物品和一个容量为V的背包，最后的答案就是

• 注意，这里中的 j 不代表已经装了重量为 j 的物品，也不代表背包中还剩余 j 的空间，只是代表背包可以装下重量 j 的物品

那么第 i 件物品放不放到背包中，有以下两种情况（状态转移方程）

第一种情况，当背包的总容量小于物品i的重量时，物品i一定无法装到背包中去，此时
第二种情况，当背包的总容量大于等于物品i的重量时，物品i可以不装到背包中，此时，也可以装到背包中，此时背包要为物品 i 腾出装下它的位置，所以此时背包的价值应该为腾出空间后的背包价值加上物品i的价值，即。在为物品i腾出空间时，可能将价值更大的物品移了出去，因此需要对和进行比较，并取最大值

从上述分析可知，为了获得的值，首先需要获得的值

3 打表过程

为帮助理解，代入具体数字并列出具体打表过程
现有容量为8的背包，共4个物品，物品的重量和价值如下

1. 首先初始化边界条件：

当背包中没有物体时，有，而当背包容量为0时，有

1. 装入物体1 | i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | | 2 | 0 | | | | | | | | | | 3 | 0 | | | | | | | | | | 4 | 0 | | | | | | | | |

1. 装入物体2，其中：

1. 装入物品2和物体3，其中：

4 代码实现

1 基本代码

public static int zeroOnePack_v1(int N, int V, int[] weight, int[] value) {
    int[][] dp = new int[N + 1][V + 1];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < weight[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    return dp[N][V];
}

• 上述代码的时间复杂度和空间复杂度均为

2 最优解回溯

基本代码中无法得知具体选择了哪一件物品，因此需要根据填表的原理找出解的组成：

• 当时，说明没有选择物品i，则回到
• 当时，说明选择了物品i，则回到

代码如下

private static List<Integer> backTracking(int[][] dp, int[] weight) {
    ArrayList<Integer> picked = new ArrayList<>();
    int j = dp[0].length - 1;
    for (int i = dp.length - 1; i > 0; i--) {
        if (dp[i][j] != dp[i - 1][j]) {
            j = j - weight[i];
            picked.add(i);
        }
    }
    return picked;
}

3 空间复杂度优化

基本代码的时间复杂度已经不能再优化了，但空间复杂度可以优化到。

优化思想

• 从状态转移公式可以发现，的值只于有关，那么我们可以将二维的简化为一维的。
• 是由子问题和的值推出来的，因此我们需要以逆序来推导，这样才能保证保存的是状态的值，如果以正序来推导，那么保存的是状态的值，违反了之前的思路。

优化的代码

public static int zeroOnePack_v2(int N, int V, int[] weight, int[] value) {
    int[] dp = new int[V + 1];

    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    return dp[V];
}

Ⅱ 01背包问题——恰好装满

上述背包问题，只要求装入背包的物品总重量小于背包的重量且价值最大，而另外一种01背包问题，其要求的是装入背包的物品总重量正好等于背包的重量（即把背包装满）且价值最大。

上述两种问题的区别是在初始化的时候有所不同：

• 如果并没有要求必须把背包装满，初始化时应该将全部设为0
• 如果要求恰好装满背包，初始化时除了为0，均设为“非法”状态，可以设置为

第一种初始化比较好理解，背包不装物品，则价值均为0，而第二种初始化的原因为：

• 只有容量为0的背包才可能被重量为0的物品“恰好装满”，此时。
• 除0容量外，其它容量的背包均没有合法的解，属于未定义的状态，它们的值可以设置为，这样可以保证一定是一种恰好装满的最优解（如果有装满背包的方案）

可以通过下述填表过程帮助理解

• 现有容量为3的背包，共2个物品，物品的重量和价值如下 | 物品编号i | 1 | 2 | | —- | —- | —- | | 物品重量w | 3 | 1 | | 物品价值v | 1 | 100 |

• 装入物品，其中：

Ⅲ 01背包问题——价值最小

上述背包问题，要求装入背包的物品价值最大，而另外一种01背包问题，其要求的是装入背包的物品的价值最小/件数最少。要求装入价值最小/件数最少的背包问题，通常会要求正好装满，因为不要求装满的话，不装入物品就是价值自小的方案。

上述两种问题的区别是在初始化以及状态转移方程有所不同：

• 从上一节已经知道，如果要求恰好装满背包，初始化时除了为0，均设为“非法”状态
• 由于要求的是最小值，因此只需要将状态转移方程的max函数改为min函数
• 由于max函数改为了min函数，因此初始化时的非法状态不能设置为，而应该设置为一个对于问题来说极大的值，注意这里非法状态不能设置为，因为状态转移时计算结果可能会造成溢出而变为负值。

可以通过下述填表过程帮助理解

• 现有容量为3的背包，共3件物品，重量如下，现要求装满背包，且装入背包的物品的数量最少（求装入物品数量最少时，相当于每个物品价值为1，求装入物品价值最少） | 物品编号i | 1 | 2 | 3 | | —- | —- | —- | —- | | 物品重量w | 1 | 2 | 3 |

• 装入物品，其中：

Ⅳ 完全背包问题

1 问题描述

有种物品和一个容量为的背包，每种物品都有无限件可用。第i种物品的重量是，价值是，求将哪些物品装入背包可使物品总重量不超过背包容量的情况下价值总和最大。
完全背包问题非常类似于01背包问题，所不同的是每种物品有无限件。

2 基本思路

从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……直至取件。
如果仍按照01背包的思路，令表示当前背包容量为 j ，前 i 种物品的最佳组合所对应的价值，那么可以按照每种物品放入数量的不同策略写出状态转移方程，即

那么为了得到需要遍历所有的，代码如下：

public static int completePack_v0(int N, int V, int[] weight, int[] value) {
    int[][] dp = new int[N + 1][V + 1];

    for (int i = 1; i <= N; i++) {
        int w = weight[i - 1];
        int v = value[i - 1];
        for (int j = 1; j <= V; j++) {
            //k=0 时相当于让dp[i-1][j]参与比较，因为此时dp[i][j]一定会等于dp[i-1][j]
            for (int k = 0; k <= j / w; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w] + k * v);
            }
        }
    }

    return dp[N][V];
}

对比该算法与01背包问题中的算法，就会发现唯一的区别便是这里多了一层循环，因为01背包中，对于第 i 个物品只有选和不选两种情况，只需要从不选和选这两种选择中选出最优的即可，而完全背包问题则需要从不选和选的k种方案中选出最优解（其中），这便是最内层循环在做的事情。
上述算法的时间复杂度为，与01背包相比，由于求解每个状态的时间不是常数了，而是。

既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第种物品最多选件，于是可以把第种物品转化为件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的物品拆分方法是：把第种物品拆成费用为、价值为的若干件物品，其中k满足。这是二进制的思想，因为不管最优策略选几件第 i 种物品，总可以表示成若干个件物品的和,，这样每种物品拆分成了件物品，时间复杂度有所改进。

但是有更优的时间复杂度为的算法，状态转移方程如下：

这个状态转移方程与01背包的状态转移方程只有一个差别。
对于01背包的方程来说，需要保证的状态是由状态递推而来的，因为需要保证每件物品只选一次，保证在考虑“是否选入第 i 种物品”时，依据的是一个绝无已经选入第 i 件物品的子结果。
而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“是否加选一件第 i 种物品”时，却正需要一个可能已选入第 i 种物品的子结果，这里 j 的循环顺序必须是的顺序，因为需要使用到较小的 j 的子结果。

3 打表过程

为帮助理解，代入具体数字并列出具体打表过程
现有容量为8的背包，共2个物品，物品的重量和价值如下

装入物品，其中：

4 代码实现

1 基本代码

public static int completePack_v1(int N, int V, int[] weight, int[] value) {
    int[][] dp = new int[N + 1][V + 1];

    for (int i = 1; i <= N; i++) {
        int w = weight[i - 1];
        int v = value[i - 1];
        for (int j = 1; j <= V; j++)
            if (j < w)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w] + v);
    }

    return dp[N][V];
}

2 空间复杂度优化

对于二维数组实现的01背包问题，第二层循环（遍历背包容量）可以正序，也可以逆序。
一维数组的01背包问题，第二层循环必须逆序。
对于完全背包问题，无论二维还是一维数组实现，都必须正序。

public static int completePack_v2(int N, int V, int[] weight, int[] value) {
    int[] dp = new int[V + 1];

    for (int i = 1; i <= N; i++) {
        int w = weight[i - 1];
        int v = value[i - 1];
        for (int j = w; j <= V; j++)
            dp[j] = Math.max(dp[j], dp[j - w] + v);
    }

    return dp[V];
}