29. 背包问题：给定不同重量和价值的物品，求在给定容量的背包下，能取得的最大价值
大约 4 分钟
背包问题是一个经典的动态规划问题，通常有多种形式。最常见的是0/1 背包问题，在这个问题中，每种物品只能选择一次。我们需要在给定的背包容量下，选择一些物品，使得它们的总价值最大。
一、0/1 背包问题描述
给定 n 种物品，每种物品有一个重量 w[i] 和一个价值 v[i]。还有一个容量为 W 的背包。求在不超过背包容量的情况下，可以获得的最大总价值。
二、动态规划解决方案
动态规划是解决背包问题的常用方法。我们定义一个二维数组 dp[i][j] 来表示前 i 件物品在背包容量为 j 的情况下可以获得的最大价值。
1. 动态规划方程
- 如果不选择第
i件物品，则dp[i][j] = dp[i-1][j]。 - 如果选择第
i件物品，则dp[i][j] = dp[i-1][j-w[i]] + v[i]。
因此，状态转移方程为：
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-1][j-w[i]] + v[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])
2. 初始化
- 当背包容量
j=0时，dp[i][0] = 0，即不管有多少物品，当背包容量为 0 时，总价值都为 0。 - 当没有物品可选时，
dp[0][j] = 0，即不管背包容量是多少，价值都为 0。
3. 代码实现
public class Knapsack {
public static int knapsack(int W, int[] w, int[] v, int n) {
int[][] dp = new int[n + 1][W + 1];
// 遍历所有物品
for (int i = 1; i <= n; i++) {
// 遍历背包容量
for (int j = 1; j <= W; j++) {
if (w[i - 1] <= j) {
// 选择不放第i件物品和选择放入第i件物品的最大值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} else {
// 不能放入第i件物品
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][W];
}
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
int n = weights.length;
int maxValue = knapsack(capacity, weights, values, n);
System.out.println("The maximum value that can be put in a knapsack of capacity " + capacity + " is " + maxValue);
}
}4. 时间复杂度和空间复杂度
- 时间复杂度：
O(n * W)，其中n是物品数量，W是背包容量。我们需要计算n * W个状态。 - 空间复杂度：
O(n * W)，二维数组dp需要存储n * W个状态。
三、优化：空间优化的动态规划
在动态规划中，我们注意到 dp[i][j] 仅仅依赖于 dp[i-1][j] 和 dp[i-1][j-w[i]]，因此我们可以将 dp 数组的维度从二维优化为一维，从而减少空间复杂度。
1. 优化后的代码实现
public class KnapsackOptimized {
public static int knapsack(int W, int[] w, int[] v, int n) {
int[] dp = new int[W + 1];
for (int i = 1; i <= n; i++) {
// 需要从后往前遍历，以避免覆盖前一个状态
for (int j = W; j >= w[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
}
}
return dp[W];
}
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
int n = weights.length;
int maxValue = knapsack(capacity, weights, values, n);
System.out.println("The maximum value that can be put in a knapsack of capacity " + capacity + " is " + maxValue);
}
}2. 时间复杂度和空间复杂度
- 时间复杂度：
O(n * W)，与原来的动态规划方法相同。 - 空间复杂度：
O(W)，将二维数组优化为一维数组，节省了空间。
四、总结
0/1 背包问题是一个经典的动态规划问题，通过定义状态和状态转移方程，我们可以逐步求解出最优解。初始的动态规划算法使用二维数组存储中间状态，空间复杂度为 O(n * W)，可以进一步优化为 O(W) 的空间复杂度，这种优化在处理大规模问题时非常有用。
动态规划的思想在背包问题中体现得非常明显，能够有效地解决具有重叠子问题和最优子结构性质的问题。