当前位置：首页 > article >正文

蓝桥杯 Java B 组之背包问题（01背包、完全背包）

article 2025/2/24 13:30:08

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)。