0/1背包简单总结

0/1背包简单总结

问题：

\(n\)件物品选择性放入载重为\(C\)的背包。第\(i\)件物品的重量为\(w[i]\)，价值为\(v[i]\)。每个物品只有一件，你可以选择不放入背包，或者放入背包。请问该如何选择物品，在能保证物品总重量不超过背包载重的条件时，使物品的价值总和最大。

解：

设\(dp[i][j]\)表示前\(i\)个物品，载重\(j\)，能获得的最大价值

选：\(dp[i][j] = dp[i - 1][j - w[i]] + v[i]\)

不选：\(dp[i][j] = dp[i - 1][j]\)

可得到状态转移方程：

\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])\)

代码：

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

如数据加强，可能会\(MLE\)，考虑空间优化

可以发现，这一轮枚举存储的元素只取决于上一轮（即\(i - 1\)行）枚举存储的元素，可以得到新状态转移方程：

\(dp[j] = max(dp[j], dp[j - w[i]] + v[i])\)

此时从左往右枚举会有重复拿取现象，故从右往左枚举。

代码：

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]);