【动态规划】深入动态规划：背包问题

---

前言

什么是背包问题，怎么解决算法中的背包问题呢？

背包问题 (Knapsack problem) 是⼀种组合优化的 NP完全问题。 问题可以描述为：给定⼀组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 根据物品的个数，分为如下几类：
• 01 背包问题：每个物品只有⼀个
• 完全背包问题：每个物品有⽆限多个
• 多重背包问题：每件物品最多有 si 个
• 混合背包问题：每个物品会有上面三种情况…
• 分组背包问题：物品有 n 组，每组物品里有若干个，每组里最多选一个物品其中上述分类里面，根据背包是否装满，又分为两类：
• 不⼀定装满背包 • 背包⼀定装满 优化方案：
• 空间优化 - 滚动数组
• 单调队列优化
• 贪心优化 根据限定条件的个数，又分为两类：
• 限定条件只有⼀个：比如体积 -> 普通的背包问题
• 限定条件有两个：比如体积 + 重量 -> ⼆维费用背包问题根据不同的问法，又分为很多类：
• 输出方案
• 求方案总数
• 最优方案
• 方案可行性
其实还有很多分类，但是我们仅需了解即可。 因此，背包问题种类非常繁多，题型非常丰富，难度也是非常难以捉摸。但是，尽管种类非常多，都是从 01 背包问题演化过来的。所以，⼀定要把 01 背包问题学好。

本文主要介绍两种背包问题

• 01背包问题
• 完全背包问题

下面本文将通过例题为大家详细展开背包问题，以及背包问题在算法中的具体体现与解法

01背包例题

一、01背包

1. 题目链接：01背包
2. 题目描述：

描述
你有⼀个背包，最多能容纳的体积是V。 现在有 n 个物品，第 i 个物品的体积为 vi, 价值为 wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求⾄多能装多大价值的物品？ 输入描述： 第⼀行两个整数 n 和 V，表示物品个数和背包体积。 接下来 n 行，每行两个数 vi 和 wi，表示第i个物品的体积和价值。 输出描述： 输出有两行，第一行输出第⼀问的答案，第⼆行输出第⼆问的答案，如果无解请输出 0。
示例1 输入：
3 5
2 10
4 5
1 4
输出：
14
9
说明：装第⼀个和第三个物品时总价值最大，但是装第⼆个和第三个物品可以使得背包恰好装满且总价 值最⼤。
示例2
输入：
3 8
12 6
11 8
6 8
输出：80
说明：装第三个物品时总价值最⼤但是不满，装满背包无解

3. 解法：
   算法思路： 我们先解决第⼀问：
   状态表示：
   dp[i][j] 表⽰：从前 i 个物品中挑选，总体积「不超过」 j ，所有的选法中，能挑选出来 的最大价值。
   状态转移⽅程： 线性 dp 状态转移方程分析⽅式，⼀般都是根据「最后⼀步」的状况，来分情况讨论：
   i. 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此 时 dp[i][j] = dp[i - 1][j] ；
   ii. 选择第 i 个物品：那么我就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i]
   的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是这种状态不⼀
   定存在，因此需要特判⼀下。 综上，状态转移⽅程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]]+ w[i]) 。
   初始化： 我们多加⼀行，方便我们的初始化，此时仅需将第⼀行初始化为 0 即可。因为什么也不选，也能 满足体积不小于 j 的情况，此时的价值为 0 。
   填表顺序： 根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
   返回值： 根据「状态表⽰」，返回 dp[n][V] 。 接下来解决第⼆问： 第⼆问仅需微调⼀下 dp 过程的五步即可。 因为有可能凑不齐 j 体积的物品，因此我们把不合法的状态设置为 -1 。
   状态表示：
   dp[i][j] 表示：从前 i 个物品中挑选，总体积「正好」等于 j ，所有的选法中，能挑选出来的最大价值。
   状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。 但是在使用 dp[i - 1][j - v[i]] 的时候，不仅要判断 j >= v[i] ，又要判断 dp[i - 1][j - v[i]] 表示的情况是否存在，也就是 dp[i - 1][j - v[i]] != -1 。
   初始化： 我们多加一行，方便我们的初始化：
   i. 第⼀个格⼦为 0 ，因为正好能凑⻬体积为 0 的背包；
   ii. 但是第⼀行后面的格子都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。
   填表顺序： 根据「状态转移方程」，我们仅需「从上往下」填表即可。
   返回值： 由于最后可能凑不成体积为 V 的情况，因此返回之前需要「特判」⼀下

4. 代码示例

 public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int V = sc.nextInt();//存放体积int[] v=new int[n+1];//存放价值int[] w=new int[n+1];for(int i=1;i<=n;i++){v[i]=sc.nextInt();w[i]=sc.nextInt();}//dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品int[] dp1=new int[V+1];for(int i=1;i<=n;i++){//由于每个物品只能用一次，为了防止重复计算，需要倒序遍历for(int j=V;j>=v[i];j--){//状态转移，要么选择第i件物品，要么不选，取价值最大的dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j]);}}System.out.println(dp1[V]);//dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品int[] dp2=new int[V+1];Arrays.fill(dp2,Integer.MIN_VALUE);//没有物品时，价值为0dp2[0]=0;for(int i=1;i<=n;i++){//由于每个物品只能用一次，为了防止重复计算，需要倒序遍历for(int j=V;j>=v[i];j--){//状态转移，要么选择第i件物品，要么不选，取价值最大的dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j]);}}//如果小于0，说明不能从初始状态转移过来，无解if(dp2[V]<0){dp2[V]=0;}System.out.println(dp2[V]);}

二、分割等和子集

1. 题目链接：分割等和子集
2. 题目描述：

给你⼀个 只包含正整数 的 ⾮空 数组 nums 。请你判断是否可以将这个数组分割成两个⼦集，使得两 个⼦集的元素和相等。 ⽰例 1：输⼊：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：输⼊：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

3. 解法（动态规划）：
   算法思路： 先将问题转化成我们「熟悉」的题型。 如果数组能够被分成两个相同元素之和相同的⼦集，那么原数组必须有下⾯⼏个性质：
   i. 所有元素之和应该是⼀个偶数；
   ii. 数组中最⼤的元素应该小于所有元素总和的⼀半；
   iii. 挑选⼀些数，这些数的总和应该等于数组总和的⼀半。 根据前两个性质，我们可以提前判断数组能够被划分。根据最后⼀个性质，我们发现问题就转化成 了「01 背包」的模型：
   i. 数组中的元素只能选择⼀次；
   ii. 每个元素⾯临被选择或者不被选择的处境；
   iii. 选出来的元素总和要等于所有元素总和的⼀半。 其中，数组内的元素就是物品，总和就是背包。 那么我们就可以⽤背包模型的分析方式，来处理这道题。 请⼤家注意，「不要背」状态转移方程，因为题型变化之后，状态转移方程就会跟着变化。我们要 记住的是分析问题的模式。⽤这种分析问题的模式来解决问题。
   状态表示：
   dp[i][j] 表示在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。
   状态转移方程： ⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论：
   i. 不选择 nums[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中 选，能否凑成总和为 j 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；
   ii. 选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是⼩于等于 j 。 因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和 为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据状态表 ⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]] 。
   综上所述，两种情况下只要有一种能够凑成总和为 j ，那么这个状态就是 true 。因此，状态转移方程为：dp[i][j] = dp[i - 1][j]
   if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]]
   初始化： 由于需要用到上⼀⾏的数据，因此我们可以先把第⼀行初始化。 第⼀行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第⼀ ⾏仅需初始化第⼀个元素 dp[0][0] = true
   填表顺序： 根据「状态转移方程」，我们需要「从上往下」填写每⼀行，每⼀行的顺序是「无所谓的」。
   返回值： 根据「状态表示」，返回 dp[n][aim] 的值。 其中 n 表示数组的大小， aim 表示要凑的目标和。
   空间优化： 所有的「背包问题」，都可以进行空间上的优化。 对于 01背包类型的，我们的优化策略是：
   i. 删掉第⼀维；
   ii. 修改第二层循环的遍历顺序即可

4. 代码示例：

 public boolean canPartition1(int[] nums) {int n = nums.length, sum = 0;for (int x : nums) sum += x;if (sum % 2 == 1) return false; // 如果不能平分，直接返回 falseint aim = sum / 2;boolean[] dp = new boolean[aim + 1]; // 建表dp[0] = true; // 初始化for (int i = 1; i <= n; i++) // 填表for (int j = aim; j >= nums[i - 1]; j--) // ⼀定要注意修改遍历顺序dp[j] = dp[j] || dp[j - nums[i - 1]];return dp[aim];}

三、目标和

1. 题目链接：
2. 题目描述：

给你⼀个整数数组 nums 和⼀个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造⼀个 表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1”
。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：⼀共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：输⼊：nums = [1], target = 1 输出：1

3. 解法（动态规划）：
   算法思路： 本题可以直接用「暴搜」的方法解决。但是稍微⽤数学知识分析⼀下，就能转化成我们常见的「背 包模型」的问题。 设我们最终选取的结果中，前面加 + 号的数字之和为 a ，前⾯加 - 号的数字之和为 b ，整个数组的总和为 sum ，于是我们有：
   ▪ a + b = sum
   ▪ a - b = target
   上⾯两个式子消去 b 之后，可以得到 a = (sum + target) / 2
   也就是说，我们仅需在 nums 数组中选择⼀些数，将它们凑成和为 (sum + target) / 2 即 可。问题就变成了 416. 分割等和⼦集 这道题。 我们了可以用相同的分析模式，来处理这道题。
   状态表示：
   dp[i][j] 表示：在前 i 个数中选，总和正好等于 j ，⼀共有多少种选法。
   状态转移方程： 老规矩，根据「最后⼀个位置」的元素，结合题目的要求，我们有「选择」最后⼀个元素或者「不选择」最后⼀个元素两种策略：
   i. 不选 nums[i] ：那么我们凑成总和 j 的总方案，就要看在前 i - 1 个元素中选，凑 成总和为 j 的⽅案数。根据状态表示，此时 dp[i][j] = dp[i - 1][j] ；
   ii. 选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是小于等于 j 。 因为如果这个元素都比要凑成的总和⼤，选择它就没有意义呀。那么我们能够凑成总和为 j 的⽅案数，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据 状态表示，此时 dp[i][j] = dp[i - 1][j - nums[i]]
   综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移方程为：dp[i][j] = dp[i - 1][j]
   if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i - 1]]
   初始化： 由于需要用到「上⼀行」的数据，因此我们可以先把第⼀⾏初始化。 第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j 。只有当目标和为 0 的时候才能做到，因此第⼀行仅需初始化第⼀个元素 dp[0][0] = 1
   填表顺序： 根据「状态转移方程」，我们需要「从上往下」填写每⼀行，每⼀行的顺序是「无所谓的」。
   返回值： 根据「状态表示」，返回 dp[n][aim] 的值。 其中 n 表⽰数组的大小， aim 表示要凑的目标和。
   空间优化： 所有的「背包问题」，都可以进行空间上的优化。 对于 01背包类型的，我们的优化策略是：
   i. 删掉第⼀维；
   ii. 修改第二层循环的遍历顺序即可。

4. 代码示例：

 public int findTargetSumWays(int[] nums, int target) {int n = nums.length, sum = 0;for (int x : nums) sum += x;int aim = (sum + target) / 2;// 处理⼀下边界情况if (aim < 0 || (sum + target) % 2 == 1) return 0;int[] dp = new int[aim + 1];dp[0] = 1;for (int i = 1; i <= n; i++)for (int j = aim; j >= nums[i - 1]; j--) // 注意修改遍历顺序dp[j] += dp[j - nums[i - 1]];return dp[aim];}

四、最后一块石头的重量||

1. 题目链接：最后一块石头的重量||
2. 题目描述：

有⼀堆石头，用整数数组 stones 表示。其中 stones[i] 表⽰第 i 块⽯头的重量。 每⼀回合，从中选出任意两块⽯头，然后将它们⼀起粉碎。假设石头的重量分别为 x 和 y，且 x <=y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的⽯头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下⼀块石头。返回此石头最小的可能重量 。如果没有⽯头剩下，就返回 0。
示例 1： 输入：stones = [2,7,4,1,8,1]
输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
提示： 1 <= stones.length <= 30
1 <= stones[i] <= 100

3. 解法（动态规划）： 算法思路： 先将问题「转化」成我们熟悉的题型。
   ▪ 任意两块⽯头在⼀起粉碎，重量相同的部分会被丢掉，重量有差异的部分会被留下来。那就 相当于在原始的数据的前⾯，加上「加号」或者「减号」，是最终的结果最小即可。也就是 说把原始的石头分成两部分，两部分的和越接近越好。
   ▪ ⼜因为当所有元素的和固定时，分成的两部分越接近数组「总和的⼀半」，两者的差越小。 因此问题就变成了：在数组中选择⼀些数，让这些数的和尽量接近 sum / 2 ，如果把数看成物 品，每个数的值看成体积和价值，问题就变成了「01 背包问题」。
   状态表示：
   dp[i][j] 表示在前 i 个元素中选择，总和不超过 j，此时所有元素的「最⼤和」。
   状态转移方程： 老规矩，根据「最后⼀个位置」的元素，结合题目的要求，分情况讨论：
   i. 不选 stones[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；
   ii. 选择 stones[i] ：这种情况下是有前提条件的，此时的 stones[i] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑 成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - stones[i] 。根 据状态表示，此时 dp[i][j] = dp[i - 1][j - stones[i]] + stones[i] 。
   综上所述，我们要的是最⼤价值。因此，状态转移方程为：dp[i][j] = dp[i - 1][j]
   if(j >= stones[i]) dp[i][j] = dp[i][j] + dp[i - 1][j - stones[i]] + stones[i] 。
   初始化： 由于需要用到上⼀行的数据，因此我们可以先把第⼀行初始化。 第⼀行表示「没有石子」。因此想凑成目标和 j ，最大和都是 0 。
   填表顺序： 根据「状态转移方程」，我们需要「从上往下」填写每⼀行，每⼀行的顺序是「无所谓的」。
   返回值：
   a. 根据「状态表示」，先找到最接近 sum / 2 的最⼤和 dp[n][sum / 2] ；
   b. 因为我们要的是两堆⽯⼦的差，因此返回 sum - 2 * dp[n][sum / 2] 。
   空间优化： 所有的背包问题，都可以进行「空间」上的优化。 对于 01背包类型的，我们的优化策略是：
   i. 删掉第⼀维；
   ii. 修改第⼆层循环的「遍历顺序」即可。

4. 代码示例：

 public int lastStoneWeightII(int[] stones) {int n = stones.length, sum = 0;for (int x : stones) sum += x;int m = sum / 2;int[] dp = new int[m + 1];for (int i = 1; i <= n; i++)for (int j = m; j >= stones[i - 1]; j--) // 注意修改遍历顺序dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);return sum - 2 * dp[m];}

完全背包例题

一、完全背包

1. 题目链接：完全背包
2. 题目描述：

你有⼀个背包，最多能容纳的体积是 V。
现在有 n 种物品，每种物品有任意多个，第i种物品的体积为 vi,价值为 wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？ 输⼊描述： 第⼀⾏两个整数 n 和 V，表⽰物品个数和背包体积。 接下来 n 行，每行两个数 vi 和 wi，表⽰第i种物品的体积和价值。 1 ≤ n,V ≤ 1000
输出描述： 输出有两⾏，第⼀⾏输出第⼀问的答案，第⼆⾏输出第⼆问的答案，如果⽆解请输出 0。
示例1 ：
输入：2 6 5 10
3 1
输出：10 2
示例2 ：
输入：
3 8 3 10
9 1
10 1
输出：20 0
说明：⽆法恰好装满背包。
示例3 输⼊：6 13
13 189
17 360
19 870
14 184
6 298
16 242
输出：596
189
说明：可以装 5 号物品 2 个，达到最⼤价值 298*2=596，若要求恰好装满，只能装 1 个 1 号物品， 价值为189.

3. 解法（动态规划）：
   算法思路： 背包问题的状态表示非常经典，如果大家不知道怎么来的，就把它当成⼀个模板记住吧~ 我们先解决第⼀问：
   状态表示：
   dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能挑选出来的最大价值。（这里是和 01背包⼀样哒）
   状态转移方程： 线性 dp 状态转移方程分析方式，⼀般都是根据最后一步的状况，来分情况讨论。但是最后一个 物品能选很多个，因此我们的需要分很多情况：
   i. 选 0 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j 。 此时最⼤价值为 dp[i - 1][j] ；
   ii. 选 1 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j -
   v[i] 。因为挑选了⼀个 i 物品，此时最⼤价值为 dp[i - 1][j - v[i]] + w[i] ； iii. 选 2 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j - 2 * v[i] 。因为挑选了两个 i 物品，此时最⼤价值为 dp[i - 1][j - 2 * v[i]] + 2 * w[i] ；
   iv. …
   综上，我们的状态转移方程为：
   dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j-2v[i]]+2w[i]…)
   当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优化的方向就是用⼀个或者两个状态来表⽰这⼀堆的状态，通常就是⽤数学的⽅式做⼀下等价替换。我们发 现第⼆维是有规律的变化的，因此我们去看看 dp[i][j - v[i]] 这个状态：dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i],dp[i-1][j-3v[i]]+2*w[i]…)
   我们发现，把 dp[i][j - v[i]] 加上 w[i] 正好和 dp[i][j] 中除了第⼀项以外的全部 ⼀致，因此我们可以修改我们的状态转移⽅程为：dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
   初始化： 我们多加⼀行，方便我们的初始化，此时仅需将第⼀行初始化为 0 即可。因为什么也不选，也能 满⾜体积不⼩于 j 的情况，此时的价值为 0 。
   填表顺序： 根据状态转移⽅程，我们仅需从上往下填表即可。
   返回值： 根据状态表示，返回 dp[n][V] 。
   接下来解决第⼆问： 第⼆问仅需微调⼀下 dp 过程的五步即可。 因为有可能凑不齐 j 体积的物品，因此我们把不合法的状态设置为 -1 。
   状态表示：
   dp[i][j] 表示：从前 i 个物品中挑选，总体积正好等于 j ，所有的选法中，能挑选出来的最大价值。
   状态转移方程：
   dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。 但是在使用 dp[i][j - v[i]] 的时候，不仅要判断 j >= v[i] ，又要判断 dp[i][j - v[i]] 表示的情况是否存在，也就是 dp[i][j - v[i]] != -1 。
   初始化： 我们多加⼀行，方便我们的初始化：
   i. 第⼀个格子为 0 ，因为正好能凑齐体积为 0 的背包；
   ii. 但是第⼀行后面的格子都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。
   填表顺序： 根据状态转移方程，我们仅需从上往下填表即可。
   返回值： 由于最后可能凑不成体积为 V 的情况，因此返回之前需要特判⼀下

4. 代码示例：

import java.util.Scanner;public class KnapsackProblem {// 定义常量static final int N = 1010;static int n, V;static int[] v = new int[N];static int[] w = new int[N];static int[] dp = new int[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读入数据n = scanner.nextInt();V = scanner.nextInt();for (int i = 1; i <= n; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}// 搞定第一问for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);}}System.out.println(dp[V]);// 第二问for (int j = 1; j <= V; j++) {dp[j] = Integer.MIN_VALUE;}for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);}}System.out.println(dp[V] < 0? 0 : dp[V]);scanner.close();}
}

二、 零钱兑换

1. 题目链接：零钱兑换
2. 题目描述：

给你⼀个整数数组 coins ，表示不同面额的硬币；以及⼀个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何⼀种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。
示例 1： 输⼊：coins = [1, 2, 5], amount = 11
输出：3 解释：11 = 5 + 5 + 1
示例 2：输⼊：coins = [2], amount = 3 输出：-1
⽰例 3： 输⼊：coins = [1], amount = 0 输出：0
提示：1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1 0 <= amount <= 104

3. 解法（动态规划）： 算法思路： 先将问题「转化」成我们熟悉的题型。
   i. 在⼀些物品中「挑选」⼀些出来，然后在满足某个「限定条件」下，解决⼀些问题，大概率 是「背包」模型；
   ii. 由于每⼀个物品都是无限多个的，因此是⼀个「完全背包」问题。 接下来的分析就是基于「完全背包」的⽅式来的。
   状态表示：
   dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于 j ，所有的选法中，最少的硬币个数。
   状态转移⽅程： 线性 dp 状态转移方程分析方式，⼀般都是根据「最后⼀步」的状况，来分情况讨论。但是最后一个物品能选很多个，因此我们的需要分很多情况：
   i. 选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。 此时最少的硬币个数为 dp[i - 1][j] ；
   ii. 选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - v[i] 。因为挑选了⼀个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - coins[i]] + 1 ；
   iii. 选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - 2 * coins[i]] + 2 ；
   iv. …
   结合我们在完全背包里面的优化思路，我们最终得到的状态转移方程为：
   dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。 这里教给大家⼀个技巧，就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥ ⾯的 i - 1 变成 i 即可。
   初始化： 初始化第⼀行即可。 这⾥因为取 min ，所以我们可以把无效的地方设置成无穷大 (0x3f3f3f3f)
   因为这⾥要求正好凑成总和为 j ，因此，需要把第⼀行除了第⼀个位置的元素，都设置成无穷大。
   填表顺序： 根据「状态转移方程」，我们仅需「从上往下」填表即可。
   返回值： 根据「状态表⽰」，返回 dp[n][V] 。但是要特判⼀下，因为有可能凑不到。

4. 代码示例：

public int coinChange(int[] coins, int amount) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = coins.length, INF = 0x3f3f3f3f;int[] dp = new int[amount + 1];for (int j = 1; j <= amount; j++) dp[j] = INF;for (int i = 1; i <= n; i++)for (int j = coins[i - 1]; j <= amount; j++)dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);return dp[amount] >= INF ? -1 : dp[amount];}

三、零钱兑换||

1. 题目链接：零钱兑换||
2. 题目描述：

给你⼀个整数数组 coins 表⽰不同⾯额的硬币，另给⼀个整数 amount 表示总金额。 请你计算并返回可以凑成总⾦额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 假设每⼀种⾯额的硬币有⽆限个。 题目数据保证结果符合 32 位带符号整数。
示例 1： 输入：amount = 5, coins = [1, 2, 5]
输出：4 解释：有四种方式可以凑成总⾦额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0 解释：只用面额 2 的硬币不能凑成总⾦额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
提示：1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同 0 <= amount <= 5000

3. 解法（动态规划）：
   算法思路： 先将问题「转化」成我们熟悉的题型。
   i. 在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率 是背包模型；
   ii. 由于每⼀个物品都是无限多个的，因此是⼀个「完全背包」问题。 接下来的分析就是基于「完全背包」的⽅式来的。
   状态表示：
   dp[i][j] 表⽰：从前 i 个硬币中挑选，总和正好等于 j ，⼀共有多少种选法。
   状态转移⽅程： 线性 dp 状态转移方程分析方式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。但是最后 ⼀个物品能选很多个，因此我们的需要分很多情况：
   i. 选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。 此时最少的硬币个数为 dp[i - 1][j] ；
   ii. 选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - v[i] 。因为挑选了⼀个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - coins[i]] + 1 ；
   iii. 选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j - 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j - 2 * coins[i]] + 2 ；
   iv. …
   结合我们在完全背包里面的「优化思路」，我们最终得到的状态转移⽅程为：
   dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] + 1 。 这里教给⼤家⼀个技巧，就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 里面的 i - 1 变成 i 即可。
   初始化： 初始化第⼀行即可。 第⼀行表示没有物品，没有物品正好能凑能和为 0 的情况。因此 dp[0][0] = 1 ，其余位置都 是 0 种情况。
   填表顺序： 根据「状态转移方程」，我们仅需「从上往下」填表即可。
   返回值： 根据「状态表示」，返回 dp[n][V] 。

4. 代码示例：

 public int change(int amount, int[] coins) {// 空间优化int[] dp = new int[amount + 1]; // 建表dp[0] = 1; // 初始化for (int x : coins) // 拿出物品for (int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置dp[j] += dp[j - x];return dp[amount];}

四、完全平方数

1. 题目链接：完全平方数
2. 题目描述：

给你⼀个整数 n ，返回 和为 n 的完全平方数的最少数量 。 完全平方数 是⼀个整数，其值等于另一个整数的平方；换句话说，其值等于⼀个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：输入：n = 13
输出：2
解释：13 = 4 + 9

3. 解法（动态规划）： 算法思路：
   这里给出⼀个用「拆分出相同⼦问题」的⽅式，定义⼀个状态表⽰。（用「完全背包」⽅式的解法 就仿照之前的分析模式就好啦~~）
   为了叙述方便，把和为 n 的完全平方数的最少数量简称为「最⼩数量」。
   对于 12 这个数，我们分析⼀下如何求它的最⼩数量。
   ▪ 如果 12 本身就是完全平⽅数，我们不⽤算了，直接返回 1 ；
   ▪ 但是 12 不是完全平⽅数，我们试着把问题分解⼀下：
   情况⼀：拆出来⼀个 1 ，然后看看 11 的最小数量，记为 x1 ；
   情况⼆：拆出来⼀个 4 ，然后看看 8 的最小数量，记为 x2 ；（为什么拆出来 4 ， 而不拆出来 2 呢？）
   情况三：拆出来⼀个 8 …
   其中，我们接下来求 11、8 的时候，其实又回到了原来的问题上。 因此，我们可以尝试用 dp 的策略，将 1 2 3 4 6 等等这些数的最小数量依次保存起来。再求较大的 n 的时候，直接查表，然后找出最⼩数量。
   状态表示：
   dp[i] 表示：和为 i 的完全平方数的最少数量。
   状态转移⽅程： 对于 dp[i] ，根据思路那⾥的分析我们知道，可以根据⼩于等于 i 的所有完全平方数 x 进行划分：
   ▪ x = 1 时，最⼩数量为： 1 + dp[i - 1] ；
   ▪ x = 4 时，最⼩数量为： 1 + dp[i - 4] …
   ⼀直枚举到 x <= i 为⽌。
   为了方便枚举完全平方数，我们采用下面的策略： for(int j = 1; j * j <= i; j++)
   综上所述，状态转移方程为：dp[i] = min(dp[i], dp[i - j * j] + 1)
   初始化： 当 n = 0 的时候，没法拆分，结果为 0 ； 当 n = 1 的时候，显然为 1 。
   填表顺序： 从左往右。
   返回值： 根据题意，返回 dp[n] 的值。

4. 代码示例：

public int numSquares(int n) {int[] dp = new int[n + 1];dp[1] = 1; // 初始化for (int i = 2; i <= n; i++) // 枚举每个数{dp[i] = 1 + dp[i - 1]; // ⾄少等于 1 + dp[i - 1]for (int j = 2; j * j <= i; j++) // ⽤⼩于 i 的完全平⽅数划分区间dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内 的最⼩值}// 返回结果return dp[n];}

结语
本文到这里就结束了，主要首先介绍了背包问题的相关概念，主要通过例题介绍了动态规划中背包问题的01背包与完全背包问题，实际上，各个背包问题都是相串相通的。
以上就是本文全部内容，感谢各位能够看到最后，如有问题，欢迎各位大佬在评论区指正，希望大家可以有所收获！创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！