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

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

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<List<Long>> 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<List<Long>> arr, long budget) {
        // dp[j] 表示当前预算为 j 时能获得的最大物品数量
        // 注意：j 的范围是从 0 到 budget
        long[] dp = new long[(int) budget + 1];

        // 遍历物品
        for (List<Long> 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<List<Long>> 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<List<Long>> 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
    }
}

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<List<Long>> arr, long budget) {
        // 计算所有物品可能达到的最大总物品数量
        long maxTotalItemsPossible = 0;
        for (List<Long> 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<Long> 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<List<Long>> 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<List<Long>> 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<List<Long>> 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
    }
}