最大化给定数组值的结果

Question

我有一个值数组，例如:

[[x,y], [x1,y1]]每个元素包含两个值，amount需要在第0个索引处支付，items可以在第1个索引处收集。此外，我有一个budget的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背包问题的一个变体。

• 每件商品的成本为"重量">
• 预算变成了"总权重">
• 您可以收集的物品数量成为"值";

编辑

如果总权重很大，并且不能使用传统的动态规划方法，则可以重新定义状态以获得解决方案，如下所示。