背包 dp 学习笔记

背包类问题是动态规划中的一类重要问题

1. 01 背包

有 \(n\) 件物品和一个容量为 \(v\) 的背包。第 \(i\) 件物品的费用是 \(c_i\)，价值是 \(w_i\)。求解将哪些物品装入背包可使价值总和最大。

1.1 基本思路

我们首先定义此问题的 dp 状态 \(f_{i,j}\) 表示前 \(i\) 件物品放入一个容量为 \(j\) 的背包的最大价值。

接下来，我们考虑它的状态转移方程是什么。我们假设此时有前 \(i\) 件物品，背包容量为 \(j\)。如果我们此时只看第 \(i\) 件物品，有以下两种选择：

• 如果不选第 \(i\) 件物品，那么此时背包就只能放入前 \(i-1\) 件中的某些物品，由于没有放入第 \(i\) 件物品，不占用空间，所以背包容量仍为 \(j\)。此是问题就被转换为了将前 \(i-1\) 件物品放入一个容量为 \(j\) 的背包的最大价值，即 dp 状态 \(f_{i-1,j}\)。

• 如果此时选入第 \(i\) 件物品，那么就会占用 \(c_i\) 的空间，也就是说前 \(i-1\) 件物品最多只能占用 \(j-c_i\) 的空间，所以此时前 \(i-1\) 件物品的最大价值为 \(f_{i-1,j-c_i}\)。因为此时选入了第 \(i\) 件物品，那么就要加上它的价值，所以最终选入第 \(i\) 件物品的最大价值为 \(f_{i-1,j-c_i}+w_i\)。

现在我们易得状态转移方程为 \(f_{i,j}\gets\max{f_{i-1,j},f_{i-1,j-c_i}+w_i}\)。由于只有选与不选两种决策，分别与 \(0\) 和 \(1\) 对应，故称之为 01 背包问题。

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=v;j++)
	{
    	if(j>=c[i])
    	{
    		dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
		}
		else dp[i][j]=dp[i-1][j];
	}
}