背包问题

最后一个物品选多少个

1. 01背包

特点：每件物品仅用一次(最多)
有$N$个物品, 和容量是$V$的背包,每个物品有两个属性体积:$v_i$, 价值:$W_i$。
问题:在背包能装得下的条件下，能挑出来的最大价值之和是多少？

• 状态表示$~f(i, j)~$

  • 集合
    • 所有选法
    • 条件
      • ①只从前$~i~$个物品中选
      • ②总体积$~\leqslant j$
  • 属性(集合存的哪一个属性？[Max, Min, Number]

• 状态计算

  • 集合的划分(不重 不漏)
    • 不含$i$的选法
    • 包含$i$的选法
      • 从$1~to~i$中选，不含i ----> 从$1~to~i-1$中选，总体积不超过j—>$f(i-1, j)$
      • 从$1~to~i$中选，包含i ----> 从$1~to~i-1$中选，总体积不超过$j-v_i$—>$f(i-1, j-v_i)$,加上第i个物品价值$W_i$
      • $f(i, j)=Max(f(i-1, j), f(i-1, j-v_i) + W_i)$

2. 完全背包

特点：每件物品有无限个

• 状态表示$~f(i, j)~$

  • 集合

    • 所有只考虑前i个物品，且总体积不大于j的所有选法

  • 属性(集合存的哪一个属性？[Max, Min, Number]

• 状态计算

  • 集合的划分(不重 不漏)
    • 第i个物品选多少个
    • 不含$i$的选法
    • 包含$i$的选法
      • 曲线救国 1. 去掉k个物品i
      • 1. 求$Max$, $f[i-1, j - k * v[i]]$
      • 1. 再加回来k个物品i $f[i - 1, j - k * v[i] ]+ k * w[i]$

3. 多重背包

特点：每件物品有个数限制

• 状态表示$~f(i, j)~$

  • 集合
    • 所有选法
    • 条件
      • ①只从前$~i~$个物品中选
      • ②总体积$~\leqslant j$
  • 属性(集合存的哪一个属性？[Max, Min, Number]

• 状态计算

  • 集合的划分(不重 不漏)
    • 不含$i$的选法
    • 包含$i$的选法
    • $f[i][j] = max(f[i - 1, j - k * v[i] ]+ k * w[i]), k=0,1,2…S_i$

4. 多重背包优化

对多重背包优化

5. 分组背包

特点：每一组里只能选一个物品

• 状态表示$~f(i, j)~$

  • 集合
    • 所有选法
    • 条件
      • ①只从前$~i~$个物品中选
      • ②总体积$~\leqslant j$
  • 属性(集合存的哪一个属性？[Max, Min, Number]

• 状态计算

  • 集合的划分(不重 不漏)
    • 第$i$组物品一个都不选
    • 第$i$组物品选第$k$个物品$f[i - 1,j - v[i,k] + w[i,k]$

线性DP

区间DP

计数类DP

数位统计DP

状态压缩DP

树形DP

记忆化搜索