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

一、问题引入

背包问题是动态规划中最经典的问题家族。0-1背包中每件物品只能选一次，完全背包中每件物品可以选无限次，而多重背包介于两者之间：每件物品有固定的数量限制。

实际问题中，多重背包的场景非常普遍：例如采购时每种商品库存有限、生产计划中每种原料有使用上限等。本文将用Java实现多重背包的二进制优化解法，将时间复杂度从O(V×Σci)优化到O(V×Σlogci)。

二、问题定义

给定N种物品和一个容量为V的背包。第i种物品的体积是wi，价值是vi，数量为ci。问如何选择物品使得背包中物品的总价值最大？

2.1 朴素解法

将每种物品的ci个副本视为ci种不同的0-1背包物品，然后运行0-1背包算法。时间复杂度为O(V × Σci)，当ci很大时效率极低。

2.2 二进制优化思想

核心洞察：任何一个正整数ci都可以用1, 2, 4, …, 2^k, remainder 这组数通过求和表示。例如：
– 13 = 1 + 2 + 4 + 6（注意最后一个是余数）

这样，原本ci个相同的物品可以被拆分为O(log ci)个”新物品”，每个新物品只能选0或1次。然后对这O(Σlog ci)个新物品运行0-1背包即可。

三、Java代码实现

import java.util.*;

/**
 * 多重背包问题求解器
 * 使用二进制优化将问题转化为0-1背包
 */
public class MultipleKnapsack {

    /**
     * 物品类
     */
    static class Item {
        int weight;   // 体积
        int value;    // 价值
        int count;    // 数量

        Item(int weight, int value, int count) {
            this.weight = weight;
            this.value = value;
            this.count = count;
        }
    }

    /**
     * 二进制优化后的物品
     */
    static class BinaryItem {
        int weight;
        int value;

        BinaryItem(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    /**
     * 将多重背包物品通过二进制拆分转化为0-1背包物品
     *
     * @param items 原始物品列表
     * @return 二进制拆分后的物品列表
     */
    public List<BinaryItem> binaryDecomposition(List<Item> items) {
        List<BinaryItem> binaryItems = new ArrayList<>();

        for (Item item : items) {
            int count = item.count;
            int k = 1; // 从1开始拆分

            // 二进制拆分：1, 2, 4, 8, ...
            while (k <= count) {
                binaryItems.add(new BinaryItem(
                    item.weight * k,
                    item.value * k
                ));
                count -= k;
                k *= 2;
            }

            // 剩余的个数
            if (count > 0) {
                binaryItems.add(new BinaryItem(
                    item.weight * count,
                    item.value * count
                ));
            }
        }

        return binaryItems;
    }

    /**
     * 多重背包求解（二进制优化版）
     * 时间复杂度：O(V * Σlog(ci))
     * 空间复杂度：O(V)
     *
     * @param capacity 背包容量
     * @param items 物品列表
     * @return 最大价值
     */
    public int solve(int capacity, List<Item> items) {
        // 二进制拆分
        List<BinaryItem> binaryItems = binaryDecomposition(items);

        // 0-1背包一维DP
        int[] dp = new int[capacity + 1];

        for (BinaryItem item : binaryItems) {
            // 倒序遍历容量（0-1背包的特点）
            for (int j = capacity; j >= item.weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
            }
        }

        return dp[capacity];
    }

    /**
     * 多重背包求解（带方案记录）
     * 返回选择的物品详情
     */
    public Result solveWithTrace(int capacity, List<Item> items) {
        List<BinaryItem> binaryItems = binaryDecomposition(items);
        int n = binaryItems.size();

        // 二维DP用于回溯方案
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            BinaryItem item = binaryItems.get(i - 1);
            for (int j = 0; j <= capacity; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选
                if (j >= item.weight) {
                    dp[i][j] = Math.max(dp[i][j], 
                        dp[i - 1][j - item.weight] + item.value);
                }
            }
        }

        // 回溯求方案
        List<Integer> selectedIndices = new ArrayList<>();
        int j = capacity;
        for (int i = n; i > 0; i--) {
            if (dp[i][j] != dp[i - 1][j]) {
                selectedIndices.add(i - 1);
                j -= binaryItems.get(i - 1).weight;
            }
        }

        return new Result(dp[n][capacity], selectedIndices);
    }

    static class Result {
        int maxValue;
        List<Integer> selectedItems;

        Result(int maxValue, List<Integer> selectedItems) {
            this.maxValue = maxValue;
            this.selectedItems = selectedItems;
        }
    }

    /**
     * 单调队列优化版多重背包
     * 时间复杂度：O(N * V)
     * 适用于容量较大、物品种类较少的情况
     */
    public int solveOptimized(int capacity, List<Item> items) {
        int[] dp = new int[capacity + 1];
        int[] oldDp = new int[capacity + 1];

        for (Item item : items) {
            System.arraycopy(dp, 0, oldDp, 0, capacity + 1);

            // 按模item.weight分组，使用单调队列优化
            for (int remainder = 0; remainder < item.weight; remainder++) {
                Deque<int[]> deque = new LinkedList<>(); // [index, value]

                for (int k = 0; remainder + k * item.weight <= capacity; k++) {
                    int j = remainder + k * item.weight;
                    int val = oldDp[j] - k * item.value;

                    // 维护单调递减队列
                    while (!deque.isEmpty() && deque.peekLast()[1] <= val) {
                        deque.pollLast();
                    }
                    deque.offerLast(new int[]{k, val});

                    // 移除超出数量限制的元素
                    while (!deque.isEmpty() && deque.peekFirst()[0] < k - item.count) {
                        deque.pollFirst();
                    }

                    dp[j] = deque.peekFirst()[1] + k * item.value;
                }
            }
        }

        return dp[capacity];
    }

    public static void main(String[] args) {
        MultipleKnapsack solver = new MultipleKnapsack();

        // 测试数据
        List<Item> items = new ArrayList<>();
        items.add(new Item(2, 3, 3));  // 重量2，价值3，数量3
        items.add(new Item(3, 4, 2));  // 重量3，价值4，数量2
        items.add(new Item(4, 5, 1));  // 重量4，价值5，数量1

        int capacity = 10;

        System.out.println("=== 多重背包（二进制优化）===");
        int maxValue = solver.solve(capacity, items);
        System.out.println("背包容量: " + capacity);
        System.out.println("最大价值: " + maxValue);

        System.out.println("\n=== 带方案追踪 ===");
        Result result = solver.solveWithTrace(capacity, items);
        System.out.println("最大价值: " + result.maxValue);
        System.out.println("选择的二进制物品索引: " + result.selectedItems);

        // 大规模测试
        System.out.println("\n=== 大规模测试（数量=1000）===");
        List<Item> largeItems = new ArrayList<>();
        largeItems.add(new Item(2, 3, 1000));
        largeItems.add(new Item(3, 4, 1000));
        int largeCapacity = 100;
        int largeValue = solver.solve(largeCapacity, largeItems);
        System.out.println("容量100，最大价值: " + largeValue);
    }
}

四、复杂度分析

五、关键技巧总结

1. 二进制拆分：任何整数都可以用2的幂次和表示，这是优化的核心
2. 一维DP数组：0-1背包使用倒序遍历实现空间优化
3. 单调队列：对于同余类进行分组，维护滑动窗口最值

六、总结

多重背包是连接0-1背包和完全背包的桥梁。通过二进制优化，我们将一个看似复杂的问题优雅地转化为了基础的0-1背包问题。这种”转化思想”在算法设计中极为重要：将不熟悉的问题转化成熟悉的问题，往往能事半功倍。