每日算法 — 使用java实现完全背包：动态规划与二进制优化

完全背包问题是经典的动态规划问题之一，与0-1背包的核心区别在于：每种物品可以选取无限次。该问题在资源分配、投资组合优化、游戏装备搭配等场景中有广泛应用。

问题定义

给定 n 种物品，每种物品有重量 weight[i] 和价值 value[i]，每种物品可以选取任意多次。背包容量为 W，求在不超过背包容量的前提下，能装入物品的最大总价值。

与0-1背包的区别

方法一：基础动态规划（O(n × W)）

核心思路

定义 dp[j] 为容量为 j 的背包能装下的最大价值。对于每种物品，由于可以无限选取，状态转移时应该正序遍历容量（与0-1背包的逆序不同），确保同一物品可以被多次选取。

状态转移方程：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

Java实现

public class CompleteKnapsack {

    /**
     * 基础动态规划解法，时间复杂度O(n * W)，空间复杂度O(W)
     * @param weights 每种物品的重量
     * @param values 每种物品的价值
     * @param W 背包容量
     * @return 最大总价值
     */
    public int maxValue(int[] weights, int[] values, int W) {
        int n = weights.length;
        // dp[j]表示容量为j的背包能获得的最大价值
        int[] dp = new int[W + 1];

        // 遍历每种物品
        for (int i = 0; i < n; i++) {
            int w = weights[i];
            int v = values[i];

            // 正序遍历容量：允许同一物品被多次选取
            for (int j = w; j <= W; j++) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }

        return dp[W];
    }

    /**
     * 扩展：记录选取方案，返回每种物品的选取数量
     */
    public int[] getSolution(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];

        // 构建dp表
        for (int i = 1; i <= n; i++) {
            int w = weights[i - 1];
            int v = values[i - 1];
            for (int j = 0; j <= W; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选第i种物品
                if (j >= w) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - w] + v); // 选第i种物品
                }
            }
        }

        // 回溯求解方案
        int[] count = new int[n];
        int j = W;
        for (int i = n; i >= 1; i--) {
            int w = weights[i - 1];
            int v = values[i - 1];
            while (j >= w && dp[i][j] == dp[i][j - w] + v) {
                count[i - 1]++;
                j -= w;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        CompleteKnapsack solution = new CompleteKnapsack();

        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int W = 8;

        System.out.println("物品重量: " + java.util.Arrays.toString(weights));
        System.out.println("物品价值: " + java.util.Arrays.toString(values));
        System.out.println("背包容量: " + W);
        System.out.println("最大价值: " + solution.maxValue(weights, values, W));

        int[] count = solution.getSolution(weights, values, W);
        System.out.println("选取方案: " + java.util.Arrays.toString(count));
    }
}

方法二：二进制优化（多重背包通用解法）

核心思路

虽然完全背包可以用O(n × W)解决，但当我们需要处理有数量限制的多重背包时，可以将物品数量拆分为二进制组合。例如13件物品可以拆分为1+2+4+6件，这样任何数量0~13都可以由这些组合表示。

对于完全背包，由于数量无限，我们可以根据背包容量计算出每种物品的最大可选数量 maxCount = W / weight[i]，然后将 maxCount 二进制拆分，转化为0-1背包问题求解。

Java实现

public class CompleteKnapsackBinaryOptimization {

    /**
     * 二进制优化解法，适用于多重背包和完全背包
     * 时间复杂度O(W * sum(log(maxCount)))，空间复杂度O(W)
     */
    public int maxValueBinaryOptimized(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) {
            int w = weights[i];
            int v = values[i];
            // 完全背包：最大数量由容量限制
            int maxCount = W / w;

            // 二进制拆分
            int k = 1;
            while (maxCount > 0) {
                int count = Math.min(k, maxCount);
                int binaryWeight = w * count;
                int binaryValue = v * count;

                // 对拆分后的组合做0-1背包（逆序遍历）
                for (int j = W; j >= binaryWeight; j--) {
                    dp[j] = Math.max(dp[j], dp[j - binaryWeight] + binaryValue);
                }

                maxCount -= count;
                k <<= 1; // k *= 2
            }
        }

        return dp[W];
    }

    /**
     * 多重背包通用版本：每种物品有数量限制
     * @param counts 每种物品的数量限制
     */
    public int maxValueMultipleKnapsack(int[] weights, int[] values, int[] counts, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) {
            int w = weights[i];
            int v = values[i];
            int maxCount = counts[i];

            int k = 1;
            while (maxCount > 0) {
                int count = Math.min(k, maxCount);
                int binaryWeight = w * count;
                int binaryValue = v * count;

                for (int j = W; j >= binaryWeight; j--) {
                    dp[j] = Math.max(dp[j], dp[j - binaryWeight] + binaryValue);
                }

                maxCount -= count;
                k <<= 1;
            }
        }

        return dp[W];
    }

    public static void main(String[] args) {
        CompleteKnapsackBinaryOptimization solution = new CompleteKnapsackBinaryOptimization();

        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int W = 8;

        System.out.println("=== 完全背包（二进制优化）===");
        System.out.println("最大价值: " + solution.maxValueBinaryOptimized(weights, values, W));

        // 多重背包示例：每种物品数量有限制
        int[] counts = {3, 2, 1, 2};
        System.out.println("\n=== 多重背包 ===");
        System.out.println("数量限制: " + java.util.Arrays.toString(counts));
        System.out.println("最大价值: " + solution.maxValueMultipleKnapsack(weights, values, counts, W));
    }
}

方法三：一维数组空间优化

核心思路

完全背包的状态转移只依赖当前行和前一行的数据，因此可以用一维数组优化空间复杂度。关键在于正序遍历容量，这样 dp[j - w] 已经被当前物品更新过，自然实现了无限选取的效果。

Java实现（更简洁的版本）

public class CompleteKnapsackOptimized {

    /**
     * 一维DP最优实现，空间复杂度O(W)
     */
    public int maxValue(int[] weights, int[] values, int W) {
        int[] dp = new int[W + 1];

        for (int i = 0; i < weights.length; 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 int countWays(int[] weights, int W) {
        int[] dp = new int[W + 1];
        dp[0] = 1; // 容量为0时有1种方案（什么都不选）

        for (int w : weights) {
            for (int j = w; j <= W; j++) {
                dp[j] += dp[j - w];
            }
        }

        return dp[W];
    }

    /**
     * 恰好装满背包的最小物品数
     */
    public int minItems(int[] weights, int W) {
        int[] dp = new int[W + 1];
        // 初始化为无穷大，dp[0] = 0
        for (int i = 1; i <= W; i++) {
            dp[i] = Integer.MAX_VALUE / 2;
        }

        for (int w : weights) {
            for (int j = w; j <= W; j++) {
                dp[j] = Math.min(dp[j], dp[j - w] + 1);
            }
        }

        return dp[W] >= Integer.MAX_VALUE / 2 ? -1 : dp[W];
    }

    public static void main(String[] args) {
        CompleteKnapsackOptimized solution = new CompleteKnapsackOptimized();

        int[] weights = {1, 2, 5};
        int[] values = {1, 2, 5};
        int W = 5;

        System.out.println("最大价值: " + solution.maxValue(weights, values, W));
        System.out.println("恰好装满的方案数: " + solution.countWays(weights, W));
        System.out.println("恰好装满的最小物品数: " + solution.minItems(weights, W));
    }
}

复杂度分析

实际应用场景

1. 货币找零：给定面额，求凑成某金额的最少/最多纸币数
2. 装备强化：游戏中用有限材料无限强化装备的最优方案
3. 资源生产：工厂用多种机器生产产品，求最大产值
4. 投资组合：在预算内重复购买某些资产的最优配置

总结

完全背包的核心在于正序遍历容量，这使得同一物品可以被多次选取。二进制优化技巧将问题转化为0-1背包，不仅适用于完全背包，更是解决多重背包的通用方法。理解这两种背包问题的区别和联系，是掌握动态规划状态设计的关键一步。