背包问题

题目

给定一组物品，每个物品有重量 w[i] 和价值 v[i]，以及一个容量为 C 的背包。如何选择装入背包的物品，使得背包中物品的总价值最大，且总重量不超过背包容量？

实现

思路：每个物品要么装入，要么不装 注意：总重量不能超过限制 dp 定义：dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值 状态转移方程：

dp[i][j] = max(
    dp[i-1][j],                   # 不选第i个物品
    dp[i-1][j-w[i]] + v[i]        # 选第i个物品（需j≥w[i]）
)

初始化：

• dp[0][j] = 0（前 0 个物品价值为 0）
• dp[i][0] = 0（容量为 0 时价值为 0）

复杂度分析

• 时间复杂度：$O(n\ast c)$
• 空间复杂度：$O(C)$

/**
 * @param {string} s
 * @return {string}
 */
function knapsack(weights, values, C) {
    const dp = new Array(C + 1).fill(0);
    
    for (let i = 0; i < weights.length; i++) {
        for (let j = C; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[C];
}