解决预算约束下物品收集最大化问题：0/1背包算法详解

public static long solveGreedy(List<List<Long>> arr, long z) {
    // 按照成本升序排序，成本相同时按物品数量降序
    arr.sort((a, b) -> {
        int costCompare = Long.compare(a.get(0), b.get(0));
        if (costCompare == 0) {
            return Long.compare(b.get(1), a.get(1)); // 成本相同，优先选物品数量多的
        }
        return costCompare;
    });

    long totalCost = 0;
    long totalItems = 0;
    for (List<Long> item : arr) {
        long currentCost = item.get(0);
        long currentItems = item.get(1);

        if (totalCost + currentCost <= z) {
            totalCost += currentCost;
            totalItems += currentItems;
        } else {
            // 预算不足以购买当前物品，且由于已排序，后续物品成本更高，因此无法购买
            break;
        }
    }
    return totalItems;
}

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

public class MaximizeItemsWithBudget {

    /**
     * 使用0/1背包动态规划解决预算约束下物品收集最大化问题。
     *
     * @param items 物品列表，每个元素为 [成本, 物品数量]
     * @param budget 总预算
     * @return 能收集到的最大物品数量
     */
    public static long solveKnapsack(List<List<Long>> items, long budget) {
        // dp[w] 表示在预算为 w 时，能收集到的最大物品数量
        // 数组大小为 budget + 1，因为预算可以从 0 到 budget
        long[] dp = new long[(int) budget + 1]; // 注意：budget可能很大，需要考虑long类型转换为int的限制

        // 初始化 dp 数组，所有元素默认为 0

        // 遍历每一个物品
        for (List<Long> item : items) {
            long currentCost = item.get(0);
            long currentItems = item.get(1);

            // 从最大预算开始向下遍历，确保每个物品只被考虑一次
            for (int w = (int) budget; w >= currentCost; w--) {
                // 状态转移方程：
                // dp[w] = max(不包含当前物品i时的dp[w], 包含当前物品i时的dp[w - currentCost] + currentItems)
                dp[w] = Math.max(dp[w], dp[(int) (w - currentCost)] + currentItems);
            }
        }

        // 最终结果是预算为 budget 时能收集到的最大物品数量
        return dp[(int) budget];
    }

    public static void main(String[] args) {
        // 示例1：与贪婪方法对比
        List<List<Long>> items1 = new ArrayList<>();
        items1.add(Arrays.asList(60L, 100L)); // 成本60，物品100
        items1.add(Arrays.asList(50L, 200L)); // 成本50，物品200
        long budget1 = 100L;
        // 预期结果：200 (选择 [50, 200])
        System.out.println("示例1 (预算100): 最大物品数量 = " + solveKnapsack(items1, budget1)); // 输出 200

        // 示例2：更复杂的场景
        List<List<Long>> items2 = new ArrayList<>();
        items2.add(Arrays.asList(10L, 60L));
        items2.add(Arrays.asList(20L, 100L));
        items2.add(Arrays.asList(30L, 120L));
        long budget2 = 50L;
        // 预期结果：220 (选择 [20, 100] 和 [30, 120])
        System.out.println("示例2 (预算50): 最大物品数量 = " + solveKnapsack(items2, budget2)); // 输出 220

        // 示例3：如果预算过大，dp数组可能内存溢出或计算量过大
        // List<List<Long>> items3 = ...;
        // long budget3 = 1_000_000_000_000L; // 1万亿，这会导致dp数组过大
        // System.out.println("示例3 (大预算): 最大物品数量 = " + solveKnapsack(items3, budget3)); // 此时需要特殊处理
    }
}

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

public class MaximizeItemsWithLargeBudget {

    /**
     * 使用0/1背包动态规划（针对大预算优化）解决预算约束下物品收集最大化问题。
     * 当预算Z非常大但物品总数量相对较小时适用。
     *
     * @param items 物品列表，每个元素为 [成本, 物品数量]
     * @param budget 总预算
     * @return 能收集到的最大物品数量
     */
    public static long solveKnapsackLargeBudget(List<List<Long>> items, long budget) {
        long maxPossibleItems = 0;
        for (List<Long> item : items) {
            maxPossibleItems += item.get(1); // 计算所有物品的最大总数量
        }

        // dp[v] 表示获得总物品数量 v 所需的最小总成本
        // 数组大小为 maxPossibleItems + 1
        long[] dp = new long[(int) maxPossibleItems + 1];

        // 初始化 dp 数组：dp[0] = 0，其余为 Long.MAX_VALUE
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        // 遍历每一个物品
        for (List<Long> item : items) {
            long currentCost = item.get(0);
            long currentItems = item.get(1);

            // 从最大物品数量开始向下遍历，确保每个物品只被考虑一次
            for (int v = (int) maxPossibleItems; v >= currentItems; v--) {
                // 只有当 dp[v - currentItems] 不是 Long.MAX_VALUE 时，才考虑加上 currentCost
                if (dp[(int) (v - currentItems)] != Long.MAX_VALUE) {
                    dp[v] = Math.min(dp[v], dp[(int) (v - currentItems)] + currentCost);
                }
            }
        }

        // 遍历 dp 数组，找到在预算内能获得的最大物品数量
        long maxItemsCollected = 0;
        for (int v = (int) maxPossibleItems; v >= 0; v--) {
            if (dp[v] <= budget) {
                maxItemsCollected = v;
                break; // 找到第一个满足条件的 v，即为最大值
            }
        }
        return maxItemsCollected;
    }

    public static void main(String[] args) {
        // 示例：模拟大预算场景，但物品数量不大
        List<List<Long>> items = new ArrayList<>();
        items.add(Arrays.asList(100_000_000L, 10L)); // 成本1亿，物品10
        items.add(Arrays.asList(200_000_000L, 15L)); // 成本2亿，物品15
        items.add(Arrays.asList(50_000_000L, 5L));   // 成本5千万，物品5
        long largeBudget = 300_000_000L; // 3亿预算

        // 如果用solveKnapsack，dp数组大小将是3亿+1，内存溢出
        // System.out.println("大预算示例 (传统DP): " + solveKnapsack(items, largeBudget)); // 会溢出

        // 使用优化后的方法
        System.out.println("大预算示例 (优化DP): 最大物品数量 = " + solveKnapsackLargeBudget(items, largeBudget));
        // 预期结果：20 (选择 [100M, 10] 和 [200M, 15] 组合的变种，或者 [50M, 5], [100M, 10], [100M, 10]等)
        // 实际：[100M, 10] + [200M, 15] = 300M 成本，25物品
        // [50M, 5] + [100M, 10] + [200M, 15] = 350M 成本，30物品 (超出预算)
        // 最佳是 [100M, 10] + [200M, 15] => 25 物品
        // 或者 [50M, 5] + [100M, 10] => 150M 成本，15物品
        // [50M, 5] + [200M, 15] => 250M 成本，20物品
        // 所以最优是 25 物品。
    }
}