【DP】01背包
算法-01背包
前置知识
- DP
思路
01背包一般分为两种，不妨叫做价值01背包和判断01背包。
价值01背包
01背包问题是这样的一类问题：给定一个背包的容量 m m m 和 n n n 个物品，每个物品有重量 w w w 和价值 v v v，求不超过背包容量时可以装下的最大价值。
对于这类问题，我们使用DP，设 f i , j f_{i,j} fi,j 为考虑前 i i i 个物品时总重恰好为 j j j 的最大价值和。
容易得到DP方程： f i , j = max ( f i − 1 , j , f i − 1 , j − w + v ) f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w}+v) fi,j=max(fi−1,j,fi−1,j−w+v)
判断01背包
思路类似，方程变为 f i , j = f i − 1 , j ∣ f i − 1 , j − w + v f_{i,j}=f_{i-1,j}\mid f_{i-1,j-w}+v fi,j=fi−1,j∣fi−1,j−w+v 即可
算法参数
- 时间复杂度： Θ ( n m ) \Theta(nm) Θ(nm)
- 空间复杂度： Θ ( n m ) \Theta(nm) Θ(nm)
滚动优化
滚动优化是动态规划中最常见的空间优化了。
容易发现在动态转移方程中有 f i , j = max ( f i − 1 , j , f i − 1 , j − w + v ) f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w}+v) fi,j=max(fi−1,j,fi−1,j−w+v)
注意到第一维仅仅继承上一轮循环的状态，可以把这一维删掉。
我们注意到每次从前往后枚举 j j j，前面的状态已经被更新了，于是不妨倒过来循环，此时前面的数据还是上一次的结果，拿过来用即可。
算法参数
- 时间复杂度： Θ ( n m ) \Theta(nm) Θ(nm)
- 空间复杂度： Θ ( n + m ) \Theta(n+m) Θ(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