java - 最大化给定值数组的结果

Question

我有一个值数组示例:

[[x,y], [x1,y1]] 每个元素包含两个值，我们需要在第 0 个索引处支付的 amount 和 items 我们可以在第一个索引处收集。另外，我的预算为 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 total = 0;
    long result = 0;
    for(List<Long> list : arr) {
        if(total + list.get(0) <= z) {
            total += list.get(0);
            result += list.get(1);
        } else {
            break;
        }
    }
}

解决这个问题的正确方法是什么？

Answer 1

这只是 0/1 knapsack problem 的一个变体.

• 每件元素的成本就是“重量”
• 预算成为“总重量”
• 您可以收集的元素数量将成为该元素的“值(value)”

编辑

如果总权重很大，无法使用传统的动态规划方法，可以重新定义状态来得到解决方案，如here所示.