本文共 2216 字，大约阅读时间需要 7 分钟。

1.01背包

01背包问题

一般01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

用状态表示和状态计算解决背包问题：

状态表示：f[i][j]表示使用前i个物品，体积不超过j的最大价值

状态转移：状态转移从最后一个物品分析，考虑不重不漏的情况：

1.分为使用第i个物品；

2.不使用第i个物品。

则

//二维空间for(int i = 1; i <= n; i++)	for(int j = 0; j <= m; j++)//m表示可容纳的最大体积		if(v[i] > j) f[i][j] = f[i - 1][j];		else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//v[i] <= j

     从转移状态方程来看第i层的状态方程都是从i-1层转移过来的，可以从空间上优化一下。去掉第一维，但是要保证第i层的f是使用第i-1层的f来更新，若单纯去掉第一维：

//！！！错误代码for(int i = 1; i <= n; i++)	for(int j = 0; j <= m; j++)//m表示可容纳的最大体积		if(v[i] > j) f[j] = f[j];		else f[j] = max(f[j], f[j - v[i]] + w[i]);//v[i] <= j

     在上述代码第i层时，较大的j是用更小的j来更新的，但是f[j]是从小到大来维护，因此上次代码虽然省略了第一维，但是第i层的f[j]的更新是利用第i层的f[j - v[i]]来更新的，应该使用第i-1层的！为了避免这个问题，可以将上述第二层循环从大到小来枚举即可解决这个问题：

for(int i = 1; i <= n; i++)	for(int j = m; j >= v[i]; j--)//从大到小来枚举		f[j] = max(f[j], f[j - v[i]] + w[i]);//v[i] <= j

     从大到小枚举的时候，更新f[j]时使用的f[j - v[i]]在第i层还未更新，则使用的f[j - v[i]]是上一层即i-1的状态。

二维费用01背包问题

有 N 件物品和一个容量是 V 承重是 M 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，重量是 mi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，总质量不超过背包承重，且总价值最大。输出最大价值。

用状态表示和状态计算解决背包问题：

状态表示：f[i][j][k]表示使用前i个物品，体积不超过j，重量不超过k的最大价值

状态转移：状态转移从最后一个物品分析，考虑不重不漏的情况：

1.分为使用第i个物品；

2.不使用第i个物品。

则

for(int i = 1; i <= n; i++)	for(int j = V; j >= v1[i]; j--)//从大到小来枚举		for(int k = M; k >= v2[i]; k--)			f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]);