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

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

问题描述

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

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

初始贪心尝试及其局限性

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

public static long solve(List<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 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 的情况下，能收集到的最大物品数量。

无限画

千库网旗下AI绘画创作平台

467 查看详情

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> 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 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> 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> arr, long budget) {        long maxPossibleItems = 0;        for (List 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 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> 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> 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背包问题的应用与优化的详细内容，更多请关注创想鸟其它相关文章！