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