背包模型

背包 DP 在容量限制下选择物品，核心差异是“每类物品能选几次”以及一维数组的枚举方向。

0/1 背包

每件最多选一次。dp[j] 表示容量不超过 j 的最大价值；处理重量 w、价值 v 时，倒序枚举 j：dp[j]=max(dp[j],dp[j-w]+v)。倒序保证本轮物品不会重复使用。

for (int i=0;i<n;i++)
  for (int j=W;j>=w[i];--j)
    dp[j]=max(dp[j], dp[j-w[i]]+v[i]);

完全与多重背包

完全背包每件可无限取，容量正序枚举，令同一物品可由已更新的 dp[j-w] 再次转移。多重背包每件有 k 个，可二进制拆分为若干 0/1 物品，将 O(nWk) 降为 O(nW log k)。

计数背包

求组合数时，外层物品、内层正序容量；求排列数时，外层容量、内层物品。恰好装满应初始化 dp[0]=0、其余为负无穷（最大化），而“至多装满”可初始化为 0。

整理自 XOJ《背包模型》。