[!info] related notes 动态规划 背包 DP 分割等和子集

DP 模板：01 背包

识别信号

• 每个物品最多使用一次
• 选或不选
• 有容量 / 目标和限制

二维定义

dp[i][j] = 前 i 个物品中，容量不超过 j 时的最优值 / 可行性 / 方案数

最值型二维模板

for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= m; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= w[i - 1]) {
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
}

一维优化模板

for (let i = 0; i < n; i++) {
    for (let j = m; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

为什么倒序

为了保证每个物品在同一轮里只被使用一次。

最小样例

物品重量：[1, 3, 4]

物品价值：[15, 20, 30]

容量：4

最优方案是选重量 4 的物品，价值 30；也可以选重量 1 + 3，价值 35，所以最优值是 35。

常见变形

• 可行性：能否恰好装满
• 方案数：有多少种装法
• 最小值：凑出目标的最少物品数