一、01背包
01背包问题是指类似如下题面的问题
设有N件物品,每件物品有一个重量及一个价值。同时有一个背包,最大载重量为M,今从N件物品中选取若干件,使其重量的和小于等于M,而价值的和为最大。
核心代码段:
for (int i = 1; i <= N; ++i) { for (int j = M; j >= w[i]; --j) { dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } }
这是01背包的一维做法。采取倒推的顺序。假设有一个二维数组
|C| | | |B|
| | | | |A|
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
即计算A的值,需要先计算B和C的值。
压缩成一维后,B就可以视作更新前A的值,计算A的值需要先计算更新前A的值和更新前C的值。
所以顺序是倒推。
二、完全背包
完全背包是指类似如下题面的问题。
设有N种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从N种物品中选取若干件(同一种物品可以无限选取),使其重量的和小于等于M,而价值的和为最大。
核心代码段:
for (int i = 1; i <= N; ++i) { for (int j = w[i]; j <= M; ++j) { dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } }
与01背包最大的不同,就是将顺序由倒推改为顺推。
|F| |E| |D| |C|
| | | | |B| |A|
要计算A的值,就要计算CDEF的值;要计算B的值,就要计算DEF的值;所以转化为,计算A的值要计算B和C的值。
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])
压缩成一维后,因为计算A时需要使用B的值,所以顺序是顺推。