背包问题

这篇博客主要总结一下主要的几种背包类型

01背包

最经典的背包问题,即给定$n$个大小为$v_i$价值为$w_i$的物体,有大小为$m$的空间,求可以获得的最大价值

朴素的方式是设$dp[i][j]$表示考虑到第$i$个物体体积为$j$的最大价值,答案是$dp[n][m]$

DP方程为$dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])$

可以发现$dp[i][j]$只与$dp[i-1][j]$有关,则优化空间复杂度变为$dp[j]=max(dp[j],dp[j-v[i]]+w[i])$

另外需要注意$j$需要从后往前枚举,因为$dp[j]$与$dp[j-v[i]]$有关,但$dp[j-v[i]]$应该存储的是$i-1$时的答案,如果从前往后枚举的话$dp[j-v[i]]$存储的就是$i$时的答案了,不符合我们的DP方程

1
2
3
4
for ( int i = 1; i <= n; ++ i ) 
for ( int j = m; j >= v[i]; -- j )
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m] << endl

完全背包

其实就是将01背包中的物体可以无限使用

思考发现其实只需要改一下01背包的代码

1
2
3
4
for ( int i = 1; i <= n; ++ i ) 
for ( int j = v[i]; j <= m; ++ j )
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m] << endl

为什么是正确的呢?与之前一样$dp[j-v[i]]$存储的就是$i$时的答案,再次更新就相当于$i$物体多次使用

多重背包

给每一个物体一个使用限制,即第$i$个物体可以使用$c_i$次

朴素的想法是添加$c_i$个$i$物体,但是这并不是一个很优秀的算法

可以思考使用2的某些特征,下面给出一个例子

对于有10个$i$物体,我们可以添加4个$i$物体,分别是$i$的1,2,4,3倍,这样一定可以凑出$1\leq x\leq 10$的$x$个$i$物体,而只是比普通的背包多了一个$log$而已

分组背包

每个物体都有一个组,而相同组别的物体至多使用一次,我们假设有$n$个组,每个组有$c_i$个物体

1
2
3
4
5
6
for ( int i = 1; i <= n; ++ i )
for ( int j = m; j >= 0; -- j )
for ( int k = 1; k <= c[i]; ++ k )
if ( j >= c[i][k] )
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
cout << dp[m] << endl;

这样就可以保证每个组的物体只使用一次了