01背包,完全背包

一、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的值,所以顺序是顺推。

发表评论

电子邮件地址不会被公开。 必填项已用*标注