跳到主要内容

背包问题

背包问题（Knapsack Problem）是组合优化中的经典问题。给定一组物品，每个物品具有重量和价值，要求在限定的总重量内，选择物品使得总价值最大。

0-1 背包问题​

每个物品最多选一次。

状态定义​

dp[i][j] 表示前 i 个物品，在容量为 j 时的最大价值。

状态转移方程​

  • 如果不选第 i 个：dp[i][j] = dp[i-1][j]
  • 如果选第 i 个：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

空间优化 (O(V))​

使用一维数组，并逆序遍历 j（避免重复选取）。

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        // 逆序遍历，确保第 i 个物品只选一次
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

完全背包问题​

每个物品可选无限次。

空间优化 (O(V))​

使用一维数组，并正序遍历 j（由于可以无限选取，正序正好利用了已经选过的状态）。

public int completeKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        // 正序遍历，由于可以无限选取，可以直接利用已算好的状态
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

应用：零钱兑换 (Coin Change)​

零钱兑换是背包问题的常见变体。

1. 最少硬币数 (LeetCode 322)​

  • 状态定义：dp[i] 表示凑齐金额 i 所需的最少硬币数。
  • 状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)

2. 凑齐金额的方法数 (LeetCode 518)​

  • 状态定义：dp[i] 表示凑齐金额 i 的组合数。
  • 状态转移：dp[i] += dp[i - coin]

练习​

  1. LeetCode 416：分割等和子集 (转化成 0-1 背包)
  2. LeetCode 322：零钱兑换
  3. LeetCode 518：零钱兑换 II (组合数)
  4. LeetCode 494：目标和
  5. LeetCode 377：组合总和 Ⅳ
  6. LeetCode 474：一和零 (二维背包)