01背包原理

01背包

每件物品只有一个

朴素算法

分为两种情况：①不选第i个物品$f[i-1][j]$

​ ②选第i个物品 状态方程可以由$f[i-1][j-v]+w$得到

$f[i-1][j-v]+w$表示前$i-1$个物品取总体积不超过$j-v$的最大价值加上第$i$个物品的价值($v,w$)分别表示第$i$个物品的体积和价值

for (int i = 1;i <= n;++i) {
   
	for (int j = 0;j <= m;++j) {
   
		f[i][j] = f[i - 1][j];
		if (j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
	}
}
cout << f[n][m] << endl;

优化成一维

因为对第$i$维的判断只用到了$i-1$维，所以可以用滚动数组的思想 由朴素的算法可知$i$维都是由$i-1$维转移过来的 如果对$j$从小到大枚举 计算到$f[j]$时 此时的$f[j-v[i]]$小于$f[j]$已经被更新到第$i$维 所以要对$j$从大到小枚举

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

##　完全背包

每件物品有无限多个

###　朴素算法

$f[i][j]=max(f[i][j],f[i-1][j-k\ast v[i]]+k\ast w[i])$与01背包类似

for (int i = 1;i <= n;++i) {
   
	for (int j = 0;j <= m;++j) {
   
		for (int k = 0;v[i] * k <= j;++k) {
   
			f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}
	}
}

优化做法

易知$f[i,j]=\mathrm{Max}(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,\dots )$

$f[i,j-v]=\mathrm{Max}(f[i-1,j-v],f[i-1,j-2v]+w,f[i-1,j-3v]+2w,\dots )$

所以$f[i,j]=Max(f[i-1,j],f[i,j-v]+w)$

for (int i = 1;i <= n;++i) {
   
	for (int j = 0;j <= m;++j) {
   
		f[i][j] = f[i - 1][j];
		if(j >= v[i])f[i][j] = max(f[i][j],f[i][j -v[i]] + w[i]);
	}
}

优化成一维

在计算$f[j]$时 因为$j-v[i]$小于$j$ 所以此时的$f[j-v[i]]$被更新到了第$i$维 与原式相符 所以$j$不需要从大到小枚举

for (int i = 1;i <= n;++i) {
   
	for (int j = v[i];j >= m;++j) {
   
		f[j] = max(f[j],f[j -v[i]] + w[i]);
	}
}