背包初始化
1.f[i][j]代表至多容积是j
全部初始化为0,
需要确保 V>=0
2.f[i][j]代表至少容积是j
f[0]=0,
f[i]=INF或者-INF或者0(对结果没有影响)
V可以<0
3.f[i][j]代表容积恰好等于j
f[0]=0,
f[i]=INF或者-INF或者0(对结果没有影响)
需要确保 V>=0
**01背包**
优化:
需要把体积逆序
二维费用:
完全背包
优化:
不需把体积逆序
多重背包
咕咕咕
分组背包
需要把题目抽象成n类,每类中有m中互斥的决策。
优化:
需要把体积逆序