预算约束下最大化物品收集量的正确解法问询

你的代码采用了贪心策略，但该策略无法得到最优解，举个反例就能说明问题：
比如预算z=3，物品数组是[[3,3], [2,1]]，你的代码会优先购买价格2的套餐，得到1个物品，剩余1元无法购买其他套餐，总物品数为1；但最优解是直接购买价格3的套餐，得到3个物品，显然更优。

这个问题本质是0-1背包问题：每个套餐只能选择一次，在总花费不超过预算z的前提下，最大化总物品收集数量。

动态规划解法思路 #

• 状态定义：dp[i]表示花费不超过i元时，能获得的最大物品数。
• 初始化：dp[0] = 0，其余dp元素初始为0（因为初始状态下没有花费，物品数为0）。
• 状态转移：遍历每个套餐（花费为w，可收集物品数为v），从后往前遍历预算（避免重复选择同一个套餐），对每个j从z到w，更新dp[j] = max(dp[j], dp[j - w] + v)。
• 结果获取：dp[z]就是预算z下能收集的最大物品数。

Java实现代码 #

import java.util.List;

public static long solve(List<List<Long>> arr, long z) {
    // dp[j] 表示花费不超过j元时能获得的最大物品数
    long[] dp = new long[(int) z + 1];
    
    for (List<Long> packageItem : arr) {
        long cost = packageItem.get(0);
        long items = packageItem.get(1);
        // 从后往前遍历，防止重复选择同一套餐
        for (long j = z; j >= cost; j--) {
            dp[(int) j] = Math.max(dp[(int) j], dp[(int) (j - cost)] + items);
        }
    }
    
    return dp[(int) z];
}

注意事项 #

• 如果预算z极大（比如超过1e5），上述数组可能占用过多内存，此时可以考虑空间优化，或者根据物品数量调整策略；但对于常规预算范围，该解法足够高效。
• 原贪心策略仅在分数背包（可拆分物品）或每个物品仅提供1个items的场景下有效，不适用于当前每个套餐提供不同数量items且不可拆分的场景。

内容的提问来源于stack exchange，提问作者Learner