DP背包问题模板：01背包 与 完全背包

01背包问题：

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件。

dp[i][j]：前 i 件物品装入容量为 j 的背包中得到的最大价值

对第 i 件物品，有2种前状态：

a. 选择第 i 件物品，则 dp[i][j] = dp[i-1][ j-w[i] ] + c[i]

b. 不选择第 i 件物品，则 dp[i][j] = dp[i-1][j]

得到状态转移方程：
$dp[i][j]=max\left \{ dp[i-1][ j-w[i] ]+c[i],dp[i-1][j]] \right \}$dp[i][j]=max{dp[i−1][j−w[i]]+c[i],dp[i−1][j]]}$(1≤i≤n,w[i]≤j≤V)$(1≤i≤n,w[i]≤j≤V)

01背包问题的空间优化：

可以发现，当 dp[i][j] = dp[i-1][j]，dp只是继承了上一层的；
而 当 dp[i][j] = dp[i-1][ j-w[i] ] + c[i]，dp只和上一层 位于 j 之前的有关。

所以得到新的状态转移方程：
$dp[j]=max\left \{ dp[ j-w[i] ]+c[i],dp[j]] \right \}$dp[j]=max{dp[j−w[i]]+c[i],dp[j]]}$(1≤i≤n,w[i]≤j≤V)$(1≤i≤n,w[i]≤j≤V)

i 的枚举方向依旧从1到n，但 j 的枚举方向必须从V到w[i]（逆序遍历！）

ps.未优化的二维数组形式，j 遍历顺序、逆序皆可；但优化后的一维数组形式 j 必须逆序遍历！

//二维数组形式
for(int i=1;i<=n;i++)
{
	for(int j=w[i];j<=V;j++)
	{
		dp[i][j]=max(dp[i−1][j−w[i]]+c[i],dp[i−1][j]]);
	}	
}

//一维数组形式
for(int i=1;i<=n;i++)
{
	for(int j=V;j>=w[i];j--)    //逆序遍历
	{
		dp[j]=max(dp[j−w[i]]+c[i],dp[j]]);
	}	
}

---

完全背包问题：

有n种物品，每种物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。

dp[i][j]：前 i 种物品装入容量为 j 的背包中得到的最大价值

对第 i 种物品，有2种前状态：

a. 选择第 i 种物品，由于每种物品有无穷件，所以转向dp[i][ j-w[i] ]的状态（而不再是dp[i-1][ j-w[i] ]），则 dp[i][j] = dp[i][ j-w[i] ] + c[i]

b. 不选择第 i 件物品，和01背包一样， dp[i][j] = dp[i-1][j]

得到状态转移方程：
$dp[i][j]=max\left \{ dp[i][ j-w[i] ]+c[i],dp[i-1][j]] \right \}$dp[i][j]=max{dp[i][j−w[i]]+c[i],dp[i−1][j]]}$(1≤i≤n,w[i]≤j≤V)$(1≤i≤n,w[i]≤j≤V)

完全背包问题的空间优化：

与01背包同样的，二维数组降至一维；

得到新的状态转移方程：
$dp[j]=max\left \{ dp[ j-w[i] ]+c[i],dp[j]] \right \}$dp[j]=max{dp[j−w[i]]+c[i],dp[j]]}$(1≤i≤n,w[i]≤j≤V)$(1≤i≤n,w[i]≤j≤V)

i 的枚举方向从1到n，j 的枚举方向从w[i]到V（顺序遍历！）

01背包与完全背包的一维数组形式的状态转移方程相同，但 01背包采用逆序遍历，完全背包采用顺序遍历。

其实从示意图可以看到，dp[i][j] 由 dp[i][ j-w[i] ] 求出，而后者在前者的左边(同一层)，所以 完全背包必须采用顺序遍历

for(int i=1;i<=n;i++)
{
	for(int j=w[i];j<=V;j++)    //顺序遍历
	{
		dp[j]=max(dp[j−w[i]]+c[i],dp[j]]);
	}	
}

---

摘自《算法笔记》