一直都搞不太明白动态规划的初始化,所以开个博客总结一下。
背包模型
设 \(f_{i, j}\) 为:以前 \(i\) 个物品,————
求方案数
二维
- 体积至多为 \(j\):\(f_{0,i}=1,0 \le i \le m\),其余为 \(0\)。
- 体积恰好为 \(j\):\(f_{0,0} = 1\),其余为 \(0\)。
- 体积至少为 \(j\):\(f_{0,0} = 1\),其余为 \(0\)。
一维
- 体积至多为 \(j\):\(f_{i}=1,0 \le i \le m\),其余为 \(0\)。
- 体积恰好为 \(j\):\(f_{0} = 1\),其余为 \(0\)。
- 体积至少为 \(j\):\(f_{0} = 1\),其余为 \(0\)。
求最值
二维
- 体积至多为 \(j\),求价值最大值:全都是 \(0\)。
- 体积恰好为 \(j\):
- 求价值最小值:\(f_{0,0}=0\),其余为 \(+\infty\)。
- 求价值最大值:\(f_{0,0}=0\),其余为 \(-\infty\)。
- 体积至少为 \(j\),求价值最小值:\(f_{0,0} = 0\),其余为 \(+\infty\)。
一维
- 体积至多为 \(j\),求价值最大值:全都是 \(0\)。
- 体积恰好为 \(j\):
- 求价值最小值:\(f_{0}=0\),其余为 \(+\infty\)。
- 求价值最大值:\(f_{0}=0\),其余为 \(-\infty\)。
- 体积至少为 \(j\),求价值最小值:\(f_{0} = 0\),其余为 \(+\infty\)。