0-1背包、完全背包及其变形【零神基础精讲】

来源0x3f：https://space.bilibili.com/206214

三叶姐的对背包问题的总结：【宫水三叶】详解完全背包一维空间优化推导（附背包问题攻略）https://leetcode.cn/circle/discuss/GWpXCM/

对边界条件的总结：

不同的题目，所要的答案不同， 比如：方案数，最大、小值，数字个数，能否构成？

这也就意味着 dp 数组值可以为数值，也可以是 boolean 类型

另外，同样是数值的情况下，不同的要求，也会造成不同的初始值 f【0】【0】：

• 能否构成： f【0】【0】 = True ； 0 可以构成 0

• 方案数： f【0】【0】 = 1 ； 0 组成 0 只有一种方案

• 数字个数： f【0】【0】 = 0 ； 0 组成 0 没有使用数字

• 最大、小值： 问题一般会回归到 方案数 或 数字个数问题， 一般会使用到 max/min 函数约束答案，而且会使用 ±inf 初始化来表示极端情况。 比如：力扣 279 求最小数量（f【0】【j】 的初始值也是要考虑的）

---

0-1背包、完全背包及其拓展（选/不选思想的代表）

0-1背包常见变形【至多/恰好/至少】 ：※重要

1、至多装capacity，求方案数/最大价值和

2、恰好装capacity，求方案数/最大/最小价值和

3、至少装capacity，求方案数/最小价值和

纯0-1背包问题

0-1背包问题：有N件物品和一个容量为C的背包。第i件物品的费用是v[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

dp[N][C+1]解法

import java.util.Scanner;
public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); }System.out.println(maxValue(N, C, v, w)); }private static int maxValue(int N, int C, int[] v, int[] w) {int[][] dp = new int[N][C + 1];dp[0][0] = 0;//填充第 0 位物品在 0-C 容量下的初始值for (int i = 0; i < C + 1; i++) {dp[0][i] = i >= v[0] ? w[0] : 0;}// 先遍历物品 再遍历背包for (int i = 1; i < N; i++) {for (int j = 0; j < C + 1; j++) {int n = dp[i - 1][j]; // 不选该物品int y = 0;if (j >= v[i]) {y = w[i] + dp[i - 1][j - v[i]]; // 选择该物品}dp[i][j] = Math.max(n, y);}}return dp[N - 1][C];}
}

dp[2][C+1]解法

private static int maxValue(int N, int C, int[] v, int[] w) {int[][] dp = new int[2][C + 1];dp[0][0] = 0;for (int i = 0; i < C + 1; i++) {dp[0][i] = i >= v[0] ? w[0] : 0;}for (int i = 1; i < N; i++) {for (int j = 0; j < C + 1; j++) {int n = dp[(i - 1)%2][j]; // 不选该物品int y = 0;if (j >= v[i]) {y = w[i] + dp[(i - 1)%2][j - v[i]]; // 选择该物品}dp[i%2][j] = Math.max(n, y);}}return dp[(N - 1)%2][C];}

dp[C+1]解法

private static int maxValue(int N, int C, int[] v, int[] w) {int[] dp = new int[C + 1];for (int i = 0; i < C + 1; i++) {dp[i] = i >= v[0] ? w[0] : 0;}for (int i = 1; i < N; i++) {for (int j = C; j >= 0; j--) {int n = dp[j]; // 不选该物品int y = 0;if (j >= v[i]) {y = w[i] + dp[j - v[i]]; // 选择该物品}dp[j] = Math.max(n, y);}}return dp[C];}	

494. 目标和

难度中等1515

给你一个整数数组 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

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

---

从什么都不知道的题目到0-1背包问题的推理过程：

设添加＋号的数和为p

则添加 - 号的数和为 sum-p

则 p-(sum-p) = target

==> p = (s+t)/2 => 在nums中选择一些数字，使得和恰好为p

记忆化搜索

class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target += x;if(target < 0 || target % 2 == 1) return 0;target /= 2;this.nums = nums;int n = nums.length;cache = new int[n][target+1];for (int i = 0; i < n; i++)Arrays.fill(cache[i], -1); // -1 表示没用访问过return dfs(n - 1, target);}public int dfs(int i, int c){if(i < 0) return c == 0 ? 1 : 0;if(cache[i][c] != -1) return cache[i][c];int res = 0;if(c < nums[i]) {res = dfs(i-1, c); // 没有容量装下i位置的物体了}else{res = dfs(i-1, c) + dfs(i-1, c - nums[i]);}cache[i][c] = res;return res;}
}

1:1翻译成递推（动态规划）

class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target += x;if(target < 0 || target % 2 == 1) return 0;target /= 2;int n = nums.length;int[][] f = new int[n+1][target+1];f[0][0] = 1; // 容量未0,所有数都选了for(int i = 0; i < n; i++){for(int c = 0; c <= target; c++){if(c < nums[i]){f[i+1][c] = f[i][c];}else{f[i+1][c] = f[i][c] + f[i][c-nums[i]];}}}return f[n][target];}// public int dfs(int i, int c){//     if(i < 0) return c == 0 ? 1 : 0;//     if(cache[i][c] != -1) return cache[i][c];//     int res = 0;//     if(c < nums[i]) {//         res = dfs(i-1, c); // 没有容量装下i位置的物体了//     }else{//         res = dfs(i-1, c) + dfs(i-1, c - nums[i]);//     }//     cache[i][c] = res;//     return res;// }
}

空间优化：滚动数组

(i+1) ==> (i+1) % 2

class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target += x;if(target < 0 || target % 2 == 1) return 0;target /= 2;int n = nums.length;int[][] f = new int[2][target+1];f[0][0] = 1; // 容量未0,所有数都选了for(int i = 0; i < n; i++){for(int c = 0; c <= target; c++){if(c < nums[i]){f[(i+1) % 2][c] = f[i % 2][c];}else{f[(i+1) % 2][c] = f[i % 2][c] + f[i % 2][c-nums[i]];}}}return f[n % 2][target];}
}

空间优化（一个数组）从后往前遍历背包

从后往前遍历容量c

class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target += x;if(target < 0 || target % 2 == 1) return 0;target /= 2;int n = nums.length;int[] f = new int[target+1];f[0] = 1; // 容量未0,所有数都选了for(int i = 0; i < n; i++){for(int c = target; c >= nums[i]; c--){f[c] = f[c] + f[c-nums[i]];}}return f[target];}
}

完全背包变形

纯完全背包问题

完全背包问题 ： 有 N 种物品和一个容量为 C 的背包，每种物品都有无限件。

第 i 件物品的体积是 v[i]，价值是 w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择多次的特点（在容量允许的情况下）。

import java.util.Scanner;
public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); }System.out.println(maxValue(N, C, v, w)); }private static int maxValue(int N, int C, int[] v, int[] w) {int[] dp = new int[C + 1];//先遍历物品，再遍历背包for (int i = 0; i < N; i++) {for (int j = C; j >= v[i]; j--) {//比较格子的数量等于最多可选第i件物品多少次for (int k = 0 ;; k++) {if (j < v[i] * k) {break;}dp[j] = Math.max(dp[j], dp[j - v[i] * k] + w[i] * k);}}}return dp[C];}
}

完全背包的dp[C+1]解法

    private static int maxValue(int N, int C, int[] v, int[] w) {int[] dp = new int[C + 1];for (int i = 0; i < N; i++) {// for (int j = C; j >= v[i]; j--) { // 0-1 背包问题for (int j = v[i]; j <= C; j++) { // 完全背包问题int n = dp[j]; // 不选该物品int y = w[i] + dp[j - v[i]]; // 选择该物品dp[j] = Math.max(n, y);}}return dp[C];}
}

322. 零钱兑换

难度中等2307

给你一个整数数组 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

记忆化搜索

class Solution {private int[] coins;private int[][] cache;public int coinChange(int[] coins, int amount) {this.coins = coins;int n = coins.length;cache = new int[n][amount + 1];for (int i = 0; i < n; i++)Arrays.fill(cache[i], -1); // -1 表示没用访问过int ans = dfs(n - 1, amount);return ans < Integer.MAX_VALUE / 2 ? ans : -1;}private int dfs(int i, int c) {// 当 c==0 时，表示这是一个合法的方案if (i < 0) return c == 0 ? 0 : Integer.MAX_VALUE / 2; // 除 2 是防止下面 + 1 溢出if (cache[i][c] != -1) return cache[i][c];if (c < coins[i]) return cache[i][c] = dfs(i - 1, c);return cache[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);}
}

翻译成递推

class Solution {public int coinChange(int[] coins, int amount) {int n = coins.length;int[][] f = new int[n + 1][amount + 1];Arrays.fill(f[0], Integer.MAX_VALUE / 2); // 除 2 是防止下面 + 1 溢出f[0][0] = 0;for (int i = 0; i < n; ++i)for (int c = 0; c <= amount; ++c)if (c < coins[i]) f[i + 1][c] = f[i][c];else f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - coins[i]] + 1);int ans = f[n][amount];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}

空间优化（一维数组）从前到后遍历背包

class Solution {public int coinChange(int[] coins, int amount) {int[] f = new int[amount + 1];Arrays.fill(f, Integer.MAX_VALUE / 2); // 除 2 是防止下面 + 1 溢出f[0] = 0;for (int x : coins)for (int c = x; c <= amount; ++c)f[c] = Math.min(f[c], f[c - x] + 1);int ans = f[amount];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}

练习

416. 分割等和子集

难度中等1645

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

class Solution {// 每个元素只可以取一次，元素的价值和大小就是自己本身public boolean canPartition(int[] nums) {Arrays.sort(nums);int sum = 0;for(int num : nums) sum += num;if(sum % 2 != 0) return false;int target = sum / 2; // 背包为target时，有没有价值和为target(价值和只可能 <= target)int[] dp = new int[target+1]; // 空间优化：一个数组for(int i = 0; i < nums.length; i++){for(int j = target; j >= nums[i]; j--){dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}}return dp[target] == target ? true : false;}
}

---

279. 完全平方数

难度中等1619

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

朴素完全背包解法

class Solution {private static final int INF = Integer.MAX_VALUE / 2;public int numSquares(int n) {// 将可能用到的【物品】预处理出来List<Integer> list = new ArrayList<>();for(int i = 1; i * i <= n; i++) list.add(i*i);// 问题就变成了：给定数字中，每个数字可以使用无限次，求凑出目标值n所需要的最少数字个数是多少int[][] dp = new int[list.size()+1][n+1]; // 前i个数字中，凑出数字总和j所需要的最少数字个数//当没有任何数时，除了 f[0][0] 为 0（花费 0 个数值凑出 0），其他均为无效值Arrays.fill(dp[0], INF);  dp[0][0] = 0;// dp[i][j] = min(dp[i-1][j-k*t]+k) 0 <= k*t <= j; k:选k个数字i，第i个数字数值为tfor(int i = 1; i <= list.size(); i++){int x = list.get(i-1);for(int j = 0; j <= n; j++){// 对于不选第 i 个数的情况dp[i][j] = dp[i-1][j];// 对于选 k 次第 i 个数的情况for(int k = 1; k * x <= j; k++){// 能够选择 k 个 x 的前提是剩余的数字 j - k * x 也能被凑出if(dp[i-1][j-k*x] != INF){dp[i][j] = Math.min(dp[i][j], dp[i-1][j-k*x] + k);}}}}return dp[list.size()][n];}
}

空间优化：

class Solution {private static final int INF = Integer.MAX_VALUE / 2;public int numSquares(int n) {// 将可能用到的【物品】预处理出来List<Integer> list = new ArrayList<>();for(int i = 1; i * i <= n; i++) list.add(i*i);// 问题就变成了：给定数字中，每个数字可以使用无限次，求凑出目标值n所需要的最少数字个数是多少int[] dp = new int[n+1]; // 前i个数字中，凑出数字总和j所需要的最少数字个数//当没有任何数时，除了 f[0][0] 为 0（花费 0 个数值凑出 0），其他均为无效值Arrays.fill(dp, INF);  dp[0] = 0;// dp[i][j] = min(dp[i-1][j-k*t]+k) 0 <= k*t <= j; k:选k个数字i，第i个数字数值为tfor(int i = 1; i <= list.size(); i++){int x = list.get(i-1);for(int j = x; j <= n; j++){dp[j] = Math.min(dp[j], dp[j-x] + 1);}}return dp[n];}
}

---

518. 零钱兑换 II

难度中等1005

给你一个整数数组 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

class Solution {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] + dp[j-x];}}return dp[amount];}
}