完全背包

物品可以无限拿，和 01 背包类似

我先自己想想

有点不敢相信，想了个三层循环，看了一点视频，视频提示说，状态表示和 01 背包 一模一样，就是状态计算会有点不一样

那我想还能怎么不一样，那就是分为不选，选 1 个 … 选到塞不下，那不就是套个循环了吗？还真是

事后：嗯，三层循环确实多，所以那只是朴素算法，后面优化了

状态计算

dp[i][j] = max(dp[i-1][j], ... , dp[i-1][j-k*v[i]] + k*w[i])

朴素代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][N];
 
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= m; j++) {
			for(int k = 1; k*v[i] <= j; k++) {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*v[i]] + k*w[i]);
			}
		}
	}
	cout << dp[n][m] << endl;
}

三层循环，所以要优化

优化为二重循环

f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w, ...)
f[i][j-v] = max(         f[i-1][j-v]  , f[i-1][j-2v]+w , f[i-1][j-3v]+2w, ...)

神中神来了，我觉得这个东西可以看作就是一个数学巧合，数学上的优化，不是什么理解实际意义上的优化，所以为什么要蹦出来一个 f[i][j-v]，只是为了这个巧合

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

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= m; j--) {  // attention
			if(j >= v[i]) dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
	cout << dp[n][m] << endl;
}

j 的遍历方向

为什么同样 j 用到前面的数据，01 背包 优化后要倒过来遍历，这里还是正过来呢？

我想是这样的：01 背包 中，用的是前一层，需要未更新的数据，当优化后，这一趟循环做的事更新，所以倒过来遍历可以使得用到的数据是旧数据

而这里循环一趟就是在递推呢，实际上是一种避免重复计算，所以要用最新的数据，所以正过来

或者说，如果真的倒过来遍历了，那前面的数据还没更新呢

一维优化

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	
	for(int i = 1; i <= n; i++) {
		for(int j = v[i]; j <= m; j++) {  // attention
			dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
		}
	}
	cout << dp[m] << endl;
}

完全背包，一层是枚举物品体积，一层枚举可行背包容量

我懂了，初学的时候只觉得是二维到一维的数学上的化简，但是去做了几道 完全平方数 零钱兑换 之后发现，可以做到直接写一维，是有直观理解的

可以无限取，就说明取了可选物品栏不变，如此就可以发现子问题了。也正是因为可选物品栏不变，所以后面的用前面的结果是不会错的

比如这里，枚举每一个背包容量之后，再枚举每一个物品，寻找放与不放的最值

j 的遍历方向

注意，这里又和 01 背包 不一样，j 又正着循环了，其实和前面的理由是一样的，我不厌其烦再梳理一次吧

说到底就是两个状态转移方程都不一样，那他们的代码又何必一样？反倒是别处代码如此相似是一种数学上的巧合

01 背包 那是要用的前一层，所以得未更新，倒序才是未更新；完全背包要的是当前层，所以得更新，正序才是已更新