【DP】01背包

算法-01背包

---

前置知识

• DP

---

思路

01背包一般分为两种，不妨叫做价值01背包和判断01背包。

价值01背包

01背包问题是这样的一类问题：给定一个背包的容量 $m$ 和 $n$ 个物品，每个物品有重量 $w$ 和价值 $v$，求不超过背包容量时可以装下的最大价值。
对于这类问题，我们使用DP，设 $f_{i,j}$ 为考虑前 $i$ 个物品时总重恰好为 $j$ 的最大价值和。
容易得到DP方程：$f_{i,j}=\max (f_{i-1,j},f_{i-1,j-w}+v)$

判断01背包

思路类似，方程变为 $f_{i,j}=f_{i-1,j}\mid f_{i-1,j-w}+v$ 即可

---

算法参数

• 时间复杂度：$\Theta (nm)$
• 空间复杂度：$\Theta (nm)$

---

滚动优化

滚动优化是动态规划中最常见的空间优化了。
容易发现在动态转移方程中有 $f_{i,j}=\max (f_{i-1,j},f_{i-1,j-w}+v)$
注意到第一维仅仅继承上一轮循环的状态，可以把这一维删掉。
我们注意到每次从前往后枚举 $j$，前面的状态已经被更新了，于是不妨倒过来循环，此时前面的数据还是上一次的结果，拿过来用即可。

---

算法参数

• 时间复杂度：$\Theta (nm)$
• 空间复杂度：$\Theta (n+m)$

---

实现代码

• 价值

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

• 判断

f[0]=1;
for (int i=1;i<=n;i++)for (int j=m;j>=w[i];j--)f[j]=f[j]|f[j-w[i]];

---

练习

• P1048
• P1049
• P1734