JavaScript求解无限背包问题：获取背包最大价值

看起来你卡在了经典的完全背包问题上——别担心，这是算法入门里很典型的问题，我一步步给你讲清楚。

首先先明确问题：我们有无限数量的几种胡萝卜，每种有固定重量和价格，背包有最大承重限制，要选胡萝卜（可以重复选同一种）让总价值最大。你的示例里，背包能装36kg，三种胡萝卜分别是2kg卖100、4kg卖120、7kg卖80，我们要算出最优组合的总价值。

解法思路：动态规划 #

完全背包的核心是动态规划（DP），我们用一个数组记录每个承重下的最大价值，逐步推导到目标承重：

• 定义dp[i]：表示背包承重为ikg时，能装的最大价值
• 初始化：dp[0] = 0（承重0时价值为0），其他初始为0
• 状态转移：对于每个承重i（从1到目标capacity），遍历所有胡萝卜类型，如果当前胡萝卜重量≤i，那么我们可以选择放这个胡萝卜，此时价值就是dp[i - carrot.kg] + carrot.price（剩下的i - carrot.kg承重的最大价值加上当前胡萝卜的价格），我们取这个值和原来的dp[i]的较大值更新dp[i]

完整代码实现 #

替换你原来的空函数，完整的getMaxValue应该是这样：

function getMaxValue(carrotTypes, capacity) {
    // 创建dp数组，长度为capacity+1，初始值0
    const dp = new Array(capacity + 1).fill(0);

    // 遍历每个可能的承重
    for (let i = 1; i <= capacity; i++) {
        // 遍历每种胡萝卜
        for (const carrot of carrotTypes) {
            // 如果当前胡萝卜重量不超过当前承重
            if (carrot.kg <= i) {
                // 更新dp[i]为当前值和选这个胡萝卜后的最大值
                dp[i] = Math.max(dp[i], dp[i - carrot.kg] + carrot.price);
            }
        }
    }

    // 最后返回承重为capacity时的最大价值
    return dp[capacity];
}

// 测试你的示例
let carrotTypes = [{ price: 100, kg: 2 }, { price: 120, kg: 4 }, { price: 80, kg: 7 } ];
let bagCapacity = 36; //kg
console.log(getMaxValue(carrotTypes, bagCapacity)); // 输出1800

代码逻辑拆解 #

1. dp数组初始化：我们需要从0kg到36kg每个承重都记录最大价值，所以数组长度是37（索引0到36）。
2. 外层循环遍历承重：从1kg开始，一步步计算到36kg的最大价值。
3. 内层循环遍历胡萝卜：对每个承重，检查每种胡萝卜能不能放进去，如果能，就看放进去后价值会不会更高。
4. 状态转移：比如当i=2时，放第一个胡萝卜（2kg），价值是dp[0]+100=100，比初始的0大，所以dp[2]变成100；当i=4时，我们可以选两个第一个胡萝卜（2*100=200），或者一个第二个胡萝卜（120），所以dp[4]会是200，这就是最优选择。

示例验证 #

你的示例里，最优解是全选第一种胡萝卜：36kg ÷ 2kg = 18个，总价值18*100=1800，和代码输出一致——因为第一种胡萝卜的单位重量价值（50/kg）是最高的，所以全选它是最优的。

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