基于预算限制的最大化物品收集：0/1背包问题的应用与优化

花韻仙語

发布时间：2025-11-04 12:13:01

890人浏览过

来源于php中文网

原创

基于预算限制的最大化物品收集：0/1背包问题的应用与优化

本文深入探讨了在给定预算下最大化收集物品的问题，将其建模为经典的0/1背包问题。文章将详细介绍动态规划（dp）的标准解决方案，包括状态定义、递推关系及具体实现。同时，针对预算值过大导致传统dp效率低下的情况，将提出一种优化策略，通过重新定义dp状态来有效解决。通过本文，读者将全面掌握此类资源分配问题的标准解法及其高级优化技巧。

问题定义与初步分析

在许多实际场景中，我们面临着在有限资源（如预算）下最大化收益（如物品数量）的问题。具体而言，假设我们有一个物品列表，每个物品都包含两个属性：购买所需的“金额”和购买后可获得的“数量”。我们还有一个总“预算”。目标是利用这个预算，尽可能多地收集物品。

例如，给定一个物品数组 arr = [[x,y], [x1,y1], ...]，其中 x 是金额，y 是物品数量，以及一个总预算 z。我们需要找到一个物品子集，使得这些物品的总金额不超过 z，并且它们总共提供的物品数量最大。

题目中提供了一个初步的尝试代码，该代码首先对物品进行排序：优先按金额升序排列，如果金额相同则按物品数量降序排列。然后，它贪婪地选择物品，只要总金额不超过预算就持续添加。

public static long solve(List> arr, long z) {
    arr.sort((a, b) -> {
        int z1 = Long.compare(a.get(0) , b.get(0));
        if(z1 == 0) {
            z1 = Long.compare(b.get(1) , a.get(1)); // 金额相同，按物品数量降序
        }
        return z1; // 优先按金额升序
    });

    long totalCost = 0;
    long totalItems = 0;
    for(List list : arr) {
        if(totalCost + list.get(0) <= z) {
            totalCost += list.get(0);
            totalItems += list.get(1);
        } else {
            break; // 预算不足，停止
        }
    }
    return totalItems; // 返回收集到的总物品数
}

然而，这种贪婪策略对于此类问题通常不是最优解。考虑一个例子：预算 z = 10，物品 [[7, 10], [3, 4], [3, 5]]。如果按照上述贪婪策略排序：[[3, 5], [3, 4], [7, 10]]。

选择 [3, 5]：totalCost = 3, totalItems = 5。
选择 [3, 4]：totalCost = 3 + 3 = 6, totalItems = 5 + 4 = 9。
无法选择 [7, 10] (6 + 7 > 10)。最终结果是 9 件物品。

但如果选择 [7, 10] 和 [3, 4] (或 [3, 5])，总成本为 7 + 3 = 10，总物品为 10 + 4 = 14 (或 10 + 5 = 15)，明显优于贪婪解。这表明该问题本质上是一个经典的0/1背包问题。

0/1背包问题的标准解法：动态规划

0/1背包问题是指：给定一组物品，每件物品都有自己的重量（在这里是金额）和价值（在这里是物品数量），在限定的总重量（在这里是预算）内，选择一部分物品，使得总价值最大化。每个物品只能选择一次（0或1）。

状态定义与递推关系

我们可以使用二维动态规划来解决这个问题。设 dp[i][j] 表示在前 i 个物品中选择，且总金额不超过 j 的情况下，能够获得的最大物品数量。

状态转移方程： 对于第 i 个物品（金额为 cost_i，物品数量为 items_i）：
1. 不选择第 i 个物品： 此时最大物品数量与在前 i-1 个物品中选择，且总金额不超过 j 的情况相同，即 dp[i-1][j]。
2. 选择第 i 个物品： 前提是当前预算 j 足够支付 cost_i。如果选择，则剩余预算为 j - cost_i，我们需要在前 i-1 个物品中，以 j - cost_i 的预算获得最大物品数量，再加上 items_i。即 dp[i-1][j - cost_i] + items_i。
因此，dp[i][j] 取这两种情况的最大值： dp[i][j] = max(dp[i-1][j], dp[i-1][j - cost_i] + items_i) (当 j >= cost_i 时) 如果 j
基准情况：
- dp[0][j] = 0 (没有物品可选，物品数量为0)。
- dp[i][0] = 0 (预算为0，无法购买任何物品)。

代码实现

import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;

public class KnapsackSolver {

    /**
     * 使用二维动态规划解决0/1背包问题，最大化收集物品数量。
     *
     * @param arr 物品列表，每个元素为 [金额, 物品数量]
     * @param budget 总预算
     * @return 在预算内可收集的最大物品数量
     */
    public static long solveWithDP(List> arr, long budget) {
        int n = arr.size();
        // dp[i][j] 表示考虑前 i 个物品，预算为 j 时能获得的最大物品数量
        // 注意：j 的范围是从 0 到 budget
        // 如果 budget 很大，这个二维数组会非常大，需要优化
        long[][] dp = new long[n + 1][(int) budget + 1];

        // 遍历物品
        for (int i = 1; i <= n; i++) {
            long currentCost = arr.get(i - 1).get(0); // 第 i-1 个物品的金额
            long currentItems = arr.get(i - 1).get(1); // 第 i-1 个物品的物品数量

            // 遍历预算
            for (int j = 0; j <= budget; j++) {
                // 不选择当前物品
                dp[i][j] = dp[i - 1][j];

                // 如果预算足够，尝试选择当前物品
                if (j >= currentCost) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][(int) (j - currentCost)] + currentItems);
                }
            }
        }
        return dp[n][(int) budget];
    }

    // 优化：使用一维DP数组，因为dp[i][j]只依赖于dp[i-1][...]
    // 为了避免重复选择，内层循环需要从大到小遍历预算
    public static long solveWithDP_OptimizedSpace(List> arr, long budget) {
        // dp[j] 表示当前预算为 j 时能获得的最大物品数量
        // 注意：j 的范围是从 0 到 budget
        long[] dp = new long[(int) budget + 1];

        // 遍历物品
        for (List item : arr) {
            long currentCost = item.get(0);
            long currentItems = item.get(1);

            // 遍历预算，从大到小，确保每个物品只被考虑一次
            for (int j = (int) budget; j >= currentCost; j--) {
                dp[j] = Math.max(dp[j], dp[(int) (j - currentCost)] + currentItems);
            }
        }
        return dp[(int) budget];
    }

    public static void main(String[] args) {
        List> items = new ArrayList<>();
        items.add(List.of(7L, 10L));
        items.add(List.of(3L, 4L));
        items.add(List.of(3L, 5L));
        long budget = 10;

        System.out.println("Max items (2D DP): " + solveWithDP(items, budget)); // 预期输出 15
        System.out.println("Max items (1D DP): " + solveWithDP_OptimizedSpace(items, budget)); // 预期输出 15

        List> items2 = new ArrayList<>();
        items2.add(List.of(10L, 60L));
        items2.add(List.of(20L, 100L));
        items2.add(List.of(30L, 120L));
        long budget2 = 50;
        System.out.println("Max items (2D DP, example 2): " + solveWithDP(items2, budget2)); // 预期输出 220
        System.out.println("Max items (1D DP, example 2): " + solveWithDP_OptimizedSpace(items2, budget2)); // 预期输出 220
    }
}

注意事项：

上述DP解法的时间复杂度是 O(n * budget)，空间复杂度是 O(n * budget) (二维DP) 或 O(budget) (一维DP)。
这种方法在 budget 值非常大时，会导致内存溢出或计算时间过长。例如，如果 budget 是 10^9，则 dp 数组将无法创建。

应对大预算值的优化策略

当预算 z（即背包容量）非常大，而物品数量 n 相对较小（例如 n

羚珑

京东推出的一站式AI图像处理平台

下载

重新定义DP状态

我们可以将DP状态定义为：dp[v] 表示为了获得总价值 v 所需的最小总金额。

状态定义： dp[v] 表示获得总物品数量 v 所需的最小总金额。
初始化： dp[0] = 0 (获得0件物品需要0金额)，dp[v] = infinity (对于所有 v > 0，初始状态下无法获得任何物品)。
状态转移方程： 遍历每个物品。对于每个物品 (cost_i, items_i)： dp[v] = min(dp[v], dp[v - items_i] + cost_i) 这个更新是从 v 从最大可能价值遍历到 items_i。

这种方法的关键在于，总物品数量（总价值）通常不会像总预算那样巨大。如果每个物品的物品数量 items_i 最大为 M，物品总数为 N，那么最大总物品数量不会超过 N * M。如果 N * M 远小于 budget，这种方法就非常高效。

代码实现

首先，我们需要确定所有物品可能达到的最大总物品数量。 maxPossibleItems = sum(items_i for each item)。

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class KnapsackSolverLargeBudget {

    /**
     * 针对大预算值情况的0/1背包问题解法，通过重新定义DP状态。
     * dp[v] 存储获得总物品数量 v 所需的最小金额。
     *
     * @param arr 物品列表，每个元素为 [金额, 物品数量]
     * @param budget 总预算
     * @return 在预算内可收集的最大物品数量
     */
    public static long solveWithLargeBudget(List> arr, long budget) {
        // 计算所有物品可能达到的最大总物品数量
        long maxTotalItemsPossible = 0;
        for (List item : arr) {
            maxTotalItemsPossible += item.get(1);
        }

        // dp[v] 表示获得总物品数量 v 所需的最小金额
        // 初始化为 Long.MAX_VALUE 表示不可达
        long[] dp = new long[(int) maxTotalItemsPossible + 1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0; // 获得0件物品需要0金额

        // 遍历每个物品
        for (List item : arr) {
            long currentCost = item.get(0);
            long currentItems = item.get(1);

            // 从最大可能物品数量开始向下遍历，确保每个物品只被使用一次
            for (int v = (int) maxTotalItemsPossible; v >= currentItems; v--) {
                if (dp[(int) (v - currentItems)] != Long.MAX_VALUE) { // 如果 (v - currentItems) 状态可达
                    dp[v] = Math.min(dp[v], dp[(int) (v - currentItems)] + currentCost);
                }
            }
        }

        // 找到在预算内可以获得的最大物品数量
        long maxItems = 0;
        for (int v = (int) maxTotalItemsPossible; v >= 0; v--) {
            if (dp[v] <= budget) {
                maxItems = v;
                break; // 找到第一个符合条件的 v 即为最大值
            }
        }
        return maxItems;
    }

    public static void main(String[] args) {
        List> items = new ArrayList<>();
        items.add(List.of(7L, 10L));
        items.add(List.of(3L, 4L));
        items.add(List.of(3L, 5L));
        long budget = 10;
        System.out.println("Max items (Large Budget DP): " + solveWithLargeBudget(items, budget)); // 预期输出 15

        List> items2 = new ArrayList<>();
        items2.add(List.of(10L, 60L));
        items2.add(List.of(20L, 100L));
        items2.add(List.of(30L, 120L));
        long budget2 = 50;
        System.out.println("Max items (Large Budget DP, example 2): " + solveWithLargeBudget(items2, budget2)); // 预期输出 220

        // 模拟一个大预算场景
        List> items3 = new ArrayList<>();
        items3.add(List.of(1000000000L, 10L)); // cost 10^9, items 10
        items3.add(List.of(1L, 1L)); // cost 1, items 1
        items3.add(List.of(2L, 2L)); // cost 2, items 2
        long budget3 = 1000000002L; // 10^9 + 2
        // 如果使用 O(N*budget) 会爆内存，这里 O(N * maxTotalItemsPossible)
        System.out.println("Max items (Large Budget DP, example 3): " + solveWithLargeBudget(items3, budget3)); // 预期输出 13
    }
}

这种优化策略的时间复杂度是 O(n * maxTotalItemsPossible)，空间复杂度是 O(maxTotalItemsPossible)。当 maxTotalItemsPossible 远小于 budget 时，这种方法非常有效。

总结与注意事项

在处理“给定预算最大化物品收集”这类问题时，我们需要识别其作为0/1背包问题的本质。

贪婪算法的局限性： 简单的贪婪选择（如按成本排序）通常无法得到最优解，因为它没有考虑全局最优性。
标准动态规划： 当预算 z 处于合理范围（例如 10^5 到 10^6 级别）时，使用 dp[i][j] 表示前 i 个物品、预算 j 下的最大物品数量是标准且有效的解法。空间可以优化到 O(budget)。
大预算值优化： 当预算 z 极其庞大（例如 10^9 级别），但物品数量 n 和单个物品的最大数量 M 相对较小（使得 n * M 处于合理范围）时，应重新定义DP状态为 dp[v] 表示获得总物品数量 v 所需的最小金额。这种方法将复杂度从依赖 budget 变为依赖 maxTotalItemsPossible。

选择哪种DP方法取决于具体的问题约束：