最大化预算内收集物品数量：0/1背包问题的应用与优化-java教程-PHP中文网

最大化预算内收集物品数量：0/1背包问题的应用与优化

本文深入探讨如何在给定预算下最大化收集物品数量的问题。我们将此问题映射为经典的0/1背包问题，并详细介绍其动态规划解决方案。针对预算过大导致传统dp效率低下的情况，文章还将介绍一种通过重新定义dp状态来优化的方法，并提供相应的代码示例，旨在帮助读者理解并掌握解决此类资源分配问题的专业策略。

问题描述

假设我们有一个物品列表，每个物品都由两个属性定义：购买所需的“金额”（或成本）和购买后能获得的“物品数量”（或价值）。我们还有一个总的“预算”限制。目标是在不超过预算的前提下，最大化我们能收集到的总物品数量。

例如，给定一个数组 arr = [[x,y], [x1,y1], ...]，其中 x 是金额，y 是物品数量，以及一个预算 z。我们需要找到一个子集，使得所有选定物品的金额之和不超过 z，且所有选定物品的数量之和最大。

初始贪心尝试及其局限性

在解决这类问题时，一种直观的尝试是采用贪心策略。例如，可以先对物品进行排序，优先选择金额较小的物品，或者在金额相同时优先选择物品数量较多的。原始代码中展示了这种尝试：

public static long solve(List<List<Long>> 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<Long> item : arr) {
        long cost = item.get(0);
        long items = item.get(1);
        if(totalCost + cost <= z) {
            totalCost += cost;
            totalItems += items;
        } else {
            break; // 预算不足，停止
        }
    }
    return totalItems;
}

登录后复制

这种贪心策略在某些特定问题（如分数背包问题）中是有效的，但对于0/1背包问题（每个物品只能选择一次，不能分割），它并不能保证找到最优解。例如，如果存在一个金额略大但物品数量极多的物品，贪心策略可能会因为优先选择小金额物品而错过这个最优选择。因此，我们需要更强大的方法来解决。

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

此问题是经典的0/1背包问题的一个变体：

每个物品的“金额”对应背包问题的“重量”。
每个物品的“物品数量”对应背包问题的“价值”。
总“预算”对应背包问题的“背包容量”。

动态规划是解决0/1背包问题的标准方法。

1. 定义DP状态

我们定义 dp[w] 为在不超过预算 w 的情况下，能收集到的最大物品数量。

集简云

软件集成平台，快速建立企业自动化与智能化

查看详情

2. 状态转移方程

遍历每个物品。对于当前物品 i，其金额为 cost_i，物品数量为 items_i。对于每个可能的预算 w（从 z 递减到 cost_i），我们可以选择两种策略：

不选择物品 i： 此时最大物品数量仍为 dp[w]。
选择物品 i： 此时最大物品数量为 dp[w - cost_i] + items_i。

因此，状态转移方程为： dp[w] = max(dp[w], dp[w - cost_i] + items_i)

需要注意的是，内层循环 w 必须从大到小遍历，以确保每个物品只被选择一次（0/1性质）。

3. 初始化

dp[0] = 0 (预算为0时，能收集0个物品)。所有其他 dp[w] 初始化为0。

4. 示例代码（Java）

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

public class MaximizeItemsWithBudget {

    /**
     * 使用标准0/1背包动态规划解决问题。
     *
     * @param arr 物品列表，每个元素 [金额, 物品数量]
     * @param budget 总预算
     * @return 能收集到的最大物品数量
     */
    public static long solveKnapsackDP(List<List<Long>> arr, long budget) {
        // dp[w] 表示在预算为 w 时，能收集到的最大物品数量
        // 注意：如果 budget 很大，这个数组会非常大，可能导致内存溢出或计算时间过长。
        // long[] dp = new long[(int) (budget + 1)]; // 预算可能超过 int 范围，需要注意类型转换
        // 鉴于 budget 可以是 long，这里需要考虑实际的 budget 范围。
        // 假设 budget 在 int 范围内，或者我们使用 HashMap 来模拟稀疏数组。
        // 为了演示，我们假设 budget 能够被 int 强制转换且在合理范围内。
        // 如果 budget 真的非常大，请参考下面的“处理大预算”部分。

        if (budget > Integer.MAX_VALUE) {
            // 提示：预算过大，请考虑使用优化方法
            System.err.println("Warning: Budget is too large for standard DP array. Consider optimized approach.");
            // 这里可以抛出异常或调用优化方法
            // For now, we will proceed with a smaller assumed budget for demonstration.
            // In a real scenario, this would be a critical check.
            // For this example, let's cap budget for array size, or use alternative DP if needed.
            // If budget is truly large, the below array initialization will fail.
            // We'll proceed with the assumption that budget fits into int for array indexing,
            // or that the "large budget" case is handled by the next section.
            // For the sake of a runnable example, let's assume budget is within int max for array size.
            // Or more practically, use the optimized approach for large budgets.
            // For a general tutorial, it's crucial to point this out.
            // Let's use a smaller max budget for this example to avoid runtime errors
            // but emphasize the limitation.
            // Let's cap budget to a reasonable int for the array size for demonstration.
            // If budget exceeds this, the optimized approach is necessary.
            // For this example, let's assume budget <= 10^5 or similar.
            // If budget is larger, the `dp` array will be too big.
        }

        // 假设 budget 不会超过 Integer.MAX_VALUE / 2，以避免数组过大
        // 在实际应用中，如果 budget 真的很大，需要使用下面的优化方法
        int maxBudgetForArray = (int) Math.min(budget, 1_000_000); // 示例限制，实际应根据内存决定
        long[] dp = new long[maxBudgetForArray + 1];

        for (List<Long> item : arr) {
            long cost = item.get(0);
            long items = item.get(1);

            // 从后往前遍历，确保每个物品只被选择一次
            for (int w = maxBudgetForArray; w >= cost; w--) {
                dp[w] = Math.max(dp[w], dp[(int)(w - cost)] + items);
            }
        }

        return dp[maxBudgetForArray]; // 返回最大预算下的最大物品数量
    }

    public static void main(String[] args) {
        List<List<Long>> items = new ArrayList<>();
        items.add(Arrays.asList(10L, 60L)); // cost, items
        items.add(Arrays.asList(20L, 100L));
        items.add(Arrays.asList(30L, 120L));
        long budget = 50;

        long maxItems = solveKnapsackDP(items, budget);
        System.out.println("Max items with budget " + budget + " (standard DP): " + maxItems); // Expected: 220 (20+100, 30+120 -> 50, 220)

        // Example with large budget (will trigger warning/limitation in current implementation)
        // For actual large budget, the optimized approach below is needed.
        // long largeBudget = 1_000_000_000L;
        // long maxItemsLargeBudget = solveKnapsackDP(items, largeBudget);
        // System.out.println("Max items with large budget (standard DP): " + maxItemsLargeBudget);
    }
}

登录后复制

处理大预算（大重量）的情况

当预算 z（即背包容量）非常大时，例如达到 10^9 甚至 10^12，而物品数量 N 相对较小（例如 N <= 100 或 N <= 200），标准0/1背包的 dp 数组大小会变得无法接受 (O(N * Z) 的时间和空间复杂度)。

在这种情况下，我们可以重新定义DP状态。由于物品数量 N 较小，而每个物品的“物品数量”或“价值”通常也在一个有限的范围内，我们可以将DP状态定义为：

1. 定义DP状态（优化版）

dp[v] 表示为了获得总价值（物品数量） v 所需的最小金额。

2. 状态转移方程

遍历每个物品。对于当前物品 i，其金额为 cost_i，物品数量为 items_i。对于每个可能的总价值 v（从 maxTotalItems 递减到 items_i），我们可以选择两种策略：

不选择物品 i： 此时所需最小金额仍为 dp[v]。
选择物品 i： 此时所需最小金额为 dp[v - items_i] + cost_i。

因此，状态转移方程为： dp[v] = min(dp[v], dp[v - items_i] + cost_i)

3. 初始化

dp[0] = 0 (获得0个物品需要0金额)。所有其他 dp[v] 初始化为一个足够大的值（例如 Long.MAX_VALUE），表示无法达到该价值。

4. 计算最大总物品数量

首先需要计算所有物品可能达到的最大总物品数量 maxPossibleItems。然后，在填充完 dp 数组后，从 maxPossibleItems 倒序遍历 v，找到第一个 v 使得 dp[v] <= budget。这个 v 就是在给定预算下能获得的最大物品数量。

5. 示例代码（Java）

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

public class MaximizeItemsWithBudgetOptimized {

    /**
     * 当预算非常大时，使用优化后的0/1背包动态规划解决问题。
     * DP状态定义为：dp[v] = 获得总价值 v 所需的最小金额。
     *
     * @param arr 物品列表，每个元素 [金额, 物品数量]
     * @param budget 总预算
     * @return 能收集到的最大物品数量
     */
    public static long solveKnapsackOptimized(List<List<Long>> arr, long budget) {
        long maxPossibleItems = 0;
        for (List<Long> item : arr) {
            maxPossibleItems += item.get(1); // 累加所有物品的最大数量
        }

        // dp[v] 存储获得总价值 v 所需的最小金额
        // 数组大小取决于 maxPossibleItems，通常比 budget 小很多
        long[] dp = new long[(int) (maxPossibleItems + 1)];

        // 初始化：获得0价值需要0金额，其他价值初始化为无穷大
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (List<Long> item : arr) {
            long cost = item.get(0);
            long items = item.get(1);

            // 从后往前遍历，确保每个物品只被选择一次
            for (int v = (int) maxPossibleItems; v >= items; v--) {
                if (dp[(int)(v - items)] != Long.MAX_VALUE) { // 确保 (v - items) 是可达的
                    dp[v] = Math.min(dp[v], dp[(int)(v - items)] + cost);
                }
            }
        }

        // 从最大可能的物品数量开始倒序查找，找到第一个满足预算条件的价值
        long resultMaxItems = 0;
        for (int v = (int) maxPossibleItems; v >= 0; v--) {
            if (dp[v] <= budget) {
                resultMaxItems = v;
                break;
            }
        }
        return resultMaxItems;
    }

    public static void main(String[] args) {
        List<List<Long>> items = new ArrayList<>();
        items.add(Arrays.asList(10L, 60L));
        items.add(Arrays.asList(20L, 100L));
        items.add(Arrays.asList(30L, 120L));
        long budget = 50;

        long maxItemsOptimized = solveKnapsackOptimized(items, budget);
        System.out.println("Max items with budget " + budget + " (optimized DP): " + maxItemsOptimized); // Expected: 220

        // 模拟一个大预算场景，优化方法在这种情况下更有效
        long largeBudget = 1_000_000_000L; // 10亿
        long maxItemsLargeBudgetOptimized = solveKnapsackOptimized(items, largeBudget);
        System.out.println("Max items with large budget " + largeBudget + " (optimized DP): " + maxItemsLargeBudgetOptimized); // Expected: 280 (所有物品都买得起 60+100+120)

        // 另一个例子
        List<List<Long>> items2 = new ArrayList<>();
        items2.add(Arrays.asList(1L, 10L));
        items2.add(Arrays.asList(2L, 20L));
        items2.add(Arrays.asList(3L, 30L));
        long budget2 = 4L; // 预算4

        // 理论上，我们可以选择 (1,10) + (3,30) -> cost 4, items 40
        // 或者 (1,10) + (2,20) -> cost 3, items 30
        // 或者 (2,20) + (3,30) -> cost 5, items 50 (超预算)
        // 应该选择 (1,10) + (3,30) 得到 40
        long maxItems2 = solveKnapsackOptimized(items2, budget2);
        System.out.println("Max items with budget " + budget2 + " (optimized DP): " + maxItems2); // Expected: 40
    }
}

登录后复制

总结

在预算内最大化收集物品数量的问题是经典的0/1背包问题的一个直接应用。

标准动态规划： 当预算（背包容量）相对较小，且物品数量不是特别大时，可以使用 dp[w] 表示在预算 w 下能获得的最大物品数量。其时间复杂度为 O(N * Z)，其中 N 是物品数量，Z 是预算。
优化动态规划： 当预算 Z 非常大，但物品数量 N 和总物品价值（或数量）相对较小时，可以采用 dp[v] 表示获得总价值 v 所需的最小金额。这种方法的复杂度为 O(N * V_total)，其中 V_total 是所有物品的最大可能总价值。这种方法在 Z 极大时能显著提高效率。

选择哪种动态规划方法取决于问题的具体约束：是预算 Z 还是总价值 V_total 更小。理解这两种DP状态定义及其适用场景是解决此类优化问题的关键。

以上就是最大化预算内收集物品数量：0/1背包问题的应用与优化的详细内容，更多请关注php中文网其它相关文章！