背包

0-1背包

给定一个背包的容量c和n个物品，第i个物品的体积为w[i]，价值为v[i]。每个物品选或不选，求体积和不超过capacity时的最大价值和

核心思路：枚举第i个物品选或不选

初始化一个二维数组dp，其中dp[i][j]表示在考虑前i个物品、背包容量为j的情况下的最大总价值

dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])

完全背包

给定一个背包的容量c和n种物品，第i种物品的体积为w[i]，价值为v[i]。每种物品无限次重复选，求体积和不超过capacity时的最大价值和

考虑第i个物品选不选时，可以重复选择，所以这里考虑dp[i][c]时，可能多次更新dp[i][c-w[i]] + v[i]

dp[i][c] = max(dp[i-1][c], dp[i][c-w[i]] + v[i])

  • 背包至多装capacity
    • 求方案数
    • 求最大价值和（原型）
  • 背包恰好装capacity
  • 背包最少装capacity
    • 求方案数
    • 求最小价值和
  • 其它

多重背包

多重背包和完全背包相似，只是一个物品被选取的次数有上限（不能无限选取）

分组背包

同一组内的物品至多/恰好选一个。