本文深入探讨了在给定预算下，如何最大化收集具有不同成本和价值（物品数量）的物品。我们将此问题映射为经典的0/1背包问题，并详细介绍两种动态规划解决方案：一种适用于常规预算规模，另一种则优化处理预算极大而物品总价值相对较小的情况，旨在帮助读者高效解决此类资源分配问题。
1. 问题描述与挑战
假设我们面临一个资源分配问题：给定一个物品列表，其中每个物品 i 都由一个购买成本 cost_i 和一个可获得的物品数量 items_i 组成。我们还拥有一个总预算 budget。我们的目标是在不超过此总预算的前提下，最大化我们能够收集到的物品总数量。
例如，物品列表可能表示为 [[x, y], [x1, y1], ...]，其中 x 是成本，y 是物品数量。我们需要从这个列表中选择一些物品，使得所选物品的总成本不超过 budget，并且所选物品的总数量达到最大。
2. 为什么贪心算法不适用
在面对此类选择问题时，一个常见的误区是尝试使用贪心算法。例如，一种贪心策略可能是：
- 将所有物品按照成本升序排序。如果成本相同，则按物品数量降序排序。
- 从排序后的列表中依次选择物品，只要当前物品的成本加上已选物品的总成本不超过预算，就选择该物品。
示例代码中展示的正是这种贪心策略：
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class GreedySolver {
public static long solve(List> arr, long z) {
// 贪心排序：优先选择成本低的，成本相同时优先选择物品多的
arr.sort(new Comparator>() {
@Override
public int compare(List a, List 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 item : arr) {
long currentCost = item.get(0);
long currentItems = item.get(1);
if (totalCost + currentCost <= z) { // 如果预算允许，则选择该物品
totalCost += currentCost;
totalItems += currentItems;
} else { // 否则，无法再选择更多物品
break;
}
}
return totalItems; // 返回收集到的总物品数
}
public static void main(String[] args) {
List> items = new ArrayList<>();
items.add(Arrays.asList(10L, 10L)); // 物品A: 成本10, 物品数10
items.add(Arrays.asList(100L, 100L)); // 物品B: 成本100, 物品数100
items.add(Arrays.asList(11L, 15L)); // 物品C: 成本11, 物品数15
long budget = 110;
System.out.println("贪心算法在预算 " + budget + " 下的最大物品数: " + solve(items, budget));
// 预期输出: 25 (A+C)
// 排序后可能为 A(10,10), C(11,15), B(100,100)
// 选 A (cost=10, items=10), 剩余预算100
// 选 C (cost=11, items=15), 剩余预算89
// 无法选 B (cost=100 > 89)
// 总物品数 = 10 + 15 = 25
}
} 然而，这种贪心策略无法保证获得全局最优解。考虑一个反例：
- 物品A: [成本: 10, 物品数: 10]
- 物品B: [成本: 100, 物品数: 100]
- 物品C: [成本: 11, 物品数: 15]
