背包问题

背包问题是很经典的dp问题,在许多基础的比赛中都会用到。可以这样说,背包问题就是学习dp的第一步,但是其难度对于初学者来说也并不小。

这篇文章主要介绍一下基础的01背包和完全背包。

01背包

01背包是最简单的背包问题,其大致描述为:

有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

二维dp

这里我们用一个二维数组dp[maxn][maxn] 来求解背包问题。

其中第一维表示前 i 个物品,第二维表示前 i 个物品在容量为 j 时的最大价值总和。

这里有一个状态方程:

1
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

dp[ i ][ j ]上面说过,表示的是前 i 件物品在容量为 j 时的最大价值,那么得到dp[ i ][ j ],其中就涉及到了关于第 i 件物品选和不选的问题。

当我们选择第 i 件物品时,总容量为 j ,我们需要腾出来 w[ i ] 的空间来装第 i 件物品,因此得出当选择第 i 件物品时的最大价值 dp[ i - 1 ][ j - w[ i ] ] + v[ i ]。

当我们不选择第 i 件物品时,那么之前的容量也必然为 j ,因为没有东西放进去,所以我们可以得到当不选择第 i 件物品时的最大价值 dp[ i - 1 ][ j ]。

理解了方程的意义,我们就可以写出来解决背包问题的代码了。

1
2
3
4
5
6
for(int i=1;i<=N;i++){
for(int j=1;j<=V;j++){
if(j<v[i]) dp[i][j]=dp[i-1][j];//容量太小,装不下第 i 个物品
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}
}

最终求出来的dp[N][V]即为答案。

这是用二维数组来求解最大价值。我们如果在纸上模拟这个过程,会发现在两层 for 循环的情况下,每个位置的值只会变化一次,当第 i 行求解完之后,我们就再也不会改变第 i 行的值了。

那么这对空间的要求是巨大的,我们是否可以把二维数组压缩成一位数组?答案是可以!

一维dp

我们如果在纸上模拟这个过程,会发现在两层 for 循环的情况下,每个位置的值只会变化一次,当第 i 行求解完之后,我们就再也不会改变第 i 行的值了。

上面的代码过程用图像可以表示为:

从上面代码和图片中可以看出,影响dp[ i ][ j ]的值为 dp[ i - 1][ j ] 和dp[ i - 1 ][ j - w[ i ] ],两个数的一维二维坐标均小于等于 i , j ,所以我们第一步先改变一下循环的顺序:

1
2
3
4
5
6
for(int i=1;i<=N;i++){
for(int j=V;j>=1;j--){//这里的循环顺序改变了
if(j<v[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}
}

如果表示成一维的话,那么过程就变成了:

可以发现,此时代码中 if(j<v[i]) dp[i][j]=dp[i-1][j] 已经失去了原本的作用。

然后将二维数组压缩成一位数组:

1
2
3
4
5
for(int i=1;i<=n;i++){
for(int j=V;j>=w[i];j--){//根据上面的代码,这里假如j<w[i]时,dp[j]=dp[j],可以直接省略
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}

在这里可能有人疑问,为什么循环顺序要变化?

当我们从前往后改变一维数组的值时,我们可能会改变了后面的数的正确的值,因为后面的数还会用到前面的是,从而导致最终结果偏离正确结果。

所以我们选用从后往前的方式进行遍历,前面已经说过,影响这个元素的值一维二维坐标均小于当前坐标,所以即使我们改变了后面的数值,也不会对前面的值有影响。

这样,我们就可以节省大量的空间(还在第二层循环时减少了时间)。

完全背包

有N种物品和一个容量为V的背包。第i种物品的重量是w[i],价值是v[i]。每种物品都可以无限件使用。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

完全背包和01背包最大的区别就是物品件数的改变。完全背包每种物品可以无限次使用,而01背包只是用一次。

我们再来看一下01背包一维dp时循环顺序的问题。

上面已经说过,假如第二层for循环的顺序是j++,那么最终结果会偏离正确结果。但是是怎么偏离的呢?我们继续深入探讨一下。

假如dp[ j ]<dp[ j - w[ i ] ] + v[ i ] ,那么dp[ j ]=dp[ j - w[ i ] ] + v[ i ],

然后对于 k ( j < k <= V),如果dp[ j ]影响到了dp[ k ] ,那么影响的结果一定是dp[ k ] = dp[ k - w[ i ] ] + v[ i ],其中 k - w[ i ] = j ( 只考虑直接影响 ),

所以我们可以继续递推得出dp[ k ] = dp[ j - w[ i ] ] +v[ i ] +v[ i ]=dp[ j - w[ i ] ] + 2 * v[ i ]。

这里我们就发现,v[ i ]被使用了两次,这在01背包中肯定是错误的,但是在完全背包中却没有任何问题,因为每件物品可以无限次使用,因此我们就可以得出完全背包的求解方法:

1
2
3
4
5
for(int i=1;i<=n;i++){
for(int j=w[i];j<=V;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}

这和01背包的区别只在于第二层循环的顺序。

感谢您的支持
-------------本文结束感谢您的阅读-------------