Day 1：背包问题（01背包、完全背包）
📖 一、背包问题简介
背包问题是动态规划（DP）中一个经典的优化问题，涉及物品选择和容量约束。通常分为以下几类：
- 01 背包（0/1 Knapsack）：每个物品只能选择 一次。
- 完全背包（Unbounded Knapsack）：每个物品可以被选择无限次。
- 多重背包：每个物品有固定的数量，不能超过限制。
- 分组背包：物品被分成多个组，每组只能选一个。
本次重点讨论01 背包 和 完全背包，并通过 "分割等和子集" 和 "零钱兑换 II" 来加深理解。
📖 二、01 背包问题
问题描述： 给定 N 个物品和一个容量为 W 的背包，每个物品有一个 重量 w[i] 和 价值 v[i]。求在不超过 W 的情况下，最大价值是多少？
🔹 01 背包的状态转移方程
定义 dp[i][j] 表示前 i 个物品在容量 j 下的最大价值：
- 不选第
i个物品：dp[i][j] = dp[i-1][j] - 选第
i个物品（前提：j >= w[i]）：dp[i][j] = dp[i-1][j - w[i]] + v[i] - 最终答案：
dp[N][W]
🔹 代码实现（01 背包）
public class Knapsack01 {
public int knapsack(int W, int[] weights, int[] values, int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // 不选第 i 个物品
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][W];
}
public static void main(String[] args) {
Knapsack01 knapsack = new Knapsack01();
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int W = 5;
int n = weights.length;
System.out.println("最大价值: " + knapsack.knapsack(W, weights, values, n)); // 输出 7
}
}
🔹 时间复杂度
O(n * W)，其中 n 是物品数量，W 是背包容量。
📖 三、完全背包问题
问题描述： 与 01 背包 不同，完全背包允许每个物品选取无限次。
🔹 完全背包的状态转移方程
- 不选第
i个物品：dp[i][j] = dp[i-1][j] - 选
k次第i个物品（前提：j >= k * w[i]）： dp[i][j]=max(dp[i][j],dp[i][j−k×w[i]]+k×v[i])dp[i][j] = \max(dp[i][j], dp[i][j - k \times w[i]] + k \times v[i])
优化版：
dp[i][j]=max(dp[i−1][j],dp[i][j−w[i]]+v[i])dp[i][j] = \max(dp[i-1][j], dp[i][j-w[i]] + v[i])
注意：完全背包的状态转移是从
dp[i][j-w[i]]来的，而不是dp[i-1][j-w[i]]，表示可以重复选取当前物品。
🔹 代码实现（完全背包）
public class KnapsackComplete {
public int knapsack(int W, int[] weights, int[] values, int n) {
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
for (int j = weights[i]; j <= W; j++) { // 正序遍历
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
public static void main(String[] args) {
KnapsackComplete knapsack = new KnapsackComplete();
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int W = 5;
int n = weights.length;
System.out.println("最大价值: " + knapsack.knapsack(W, weights, values, n)); // 输出 8
}
}
🔹 时间复杂度
O(n * W)，但使用了一维 dp 数组，空间复杂度从 O(n*W) 降到了 O(W)。
📖 四、练习 1：分割等和子集（Subset Sum）
题目描述： 给定一个非负整数数组 nums，判断是否可以将其分割为两个子集，使得两个子集的和相等。
🔹 思路
- 转化为 01 背包问题：
- 目标是找到一个子集，使得其和为
sum/2。 - 如果
sum为奇数，则直接返回false。 - 状态定义：
dp[j]表示能否填满容量j的背包。 - 状态转移方程：
dp[j] = dp[j] || dp[j - nums[i]]
- 目标是找到一个子集，使得其和为
🔹 代码实现
import java.util.*;
public class PartitionEqualSubsetSum {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum % 2 != 0) return false; // 奇数直接返回 false
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) { // 01 背包，倒序遍历
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
public static void main(String[] args) {
PartitionEqualSubsetSum solution = new PartitionEqualSubsetSum();
int[] nums = {1, 5, 11, 5};
System.out.println(solution.canPartition(nums)); // 输出 true
}
}
时间复杂度：O(n * sum/2)，sum 是数组和。
📖 五、练习 2：零钱兑换 II（Coin Change II）
题目描述： 给定不同面额的硬币 coins 和一个总金额 amount，求总共有多少种方式可以凑成 amount。
🔹 代码实现
public class CoinChange2 {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1; // 组合数初始化
for (int coin : coins) {
for (int j = coin; j <= amount; j++) { // 完全背包，正序遍历
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
public static void main(String[] args) {
CoinChange2 solution = new CoinChange2();
int[] coins = {1, 2, 5};
int amount = 5;
System.out.println(solution.change(amount, coins)); // 输出 4
}
}
时间复杂度：O(n * amount)。
📖 六、总结
01 背包 vs 完全背包
| 背包类型 | 状态转移 |
|---|---|
| 01 背包 | dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) |
| 完全背包 | dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) |
🎯 练习建议
- 先熟练掌握 01 背包，再理解 完全背包 的正序遍历优化。
- 多练习 变种题型，如 分割等和子集、零钱兑换 II。
