背包 DP：0-1 与完全背包

一、面试常考点

1. 0-1 与完全背包区别

每件物品用 1 次 vs 可用无限次。

2. 一维优化的遍历方向

0-1 背包容量倒序；完全背包容量正序。

二、细节介绍

1. 状态定义

dp[j] 表示容量为 j 时的最大价值。

2. 0-1 背包转移

dp[j] = max(dp[j], dp[j-w] + v)，j 从大到小。

3. 完全背包转移

同式子，j 从小到大。

三、示例代码

function knapsack01(weights, values, cap) {
  const dp = Array(cap + 1).fill(0)

  for (let i = 0; i < weights.length; i++) {
    const w = weights[i]
    const v = values[i]
    for (let j = cap; j >= w; j--) {
      dp[j] = Math.max(dp[j], dp[j - w] + v)
    }
  }

  return dp[cap]
}

四、常用应用场景

1. 资源分配

预算、时间、容量受限下收益最大化。

2. 组合计数

求方案数时可把 max 改为 +。