JZTXT

动态规划

发布时间 2023-10-01 15:55:55作者: Lil_Leap

0-1背包 最多用一次
完全背包 每件物品有无限个
多重背包 每个物品个数不一样 优化
分组背包问题

0-1背包

题目：

0-1背包一维优化
因为，状态转移中只使用了f[i-1]和f[i] ，其他的没用，所以说我们可以使用滚动数组来优化，把f[i][j]改成f[j]，不考虑其他的i的存储。
原代码

for(int i = 1;i <= n; i++)
	for(int j = 0; j <= m;j++)
	{
		f[i][j] = f[i-1][j];//保持与上一层i相同，所以直接删掉
		if(j >= v[i]) f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
	}

优化后

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

由于状态改变需要j >= v[i]，所以直接令j从v[i]开始循环。但是由于j是递增循环，j-v[i]肯定小于j，所以f[j-v[i]]指的是第i层的值。而原式是f[i-1]，所以将第二层循环改成递减。

完全背包问题

完全背包 每件物品有无限个
朴素版
image.png
k为第i个物品的个数，状态转移方程为$f[i,j] = f[i - 1], j - v[i] * k] + w[i] * k$

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 - v[i] * k] + w[i] * k);//当k = 0时即i物品不放入的情况

运行时间过长，时间复杂度较大

二维优化

image.png
由图所得，优化后状态转移方程为$f[i, j] = Max(f[i - 1, j], f[i, j - v[i]] + 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, j - v[i]] + w[i]);
	}

一维优化

类似0-1背包问题，将数组变为一维，但完全背包问题不同于0-1背包，状态转移方程中为f[i, j - v[i]]+w[i]

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

完整推导过程如上

综上，0-1背包问题与完全背包问题的区别，仅仅只在第二层循环，0-1背包中j为从大到小递减循环，完全背包中j为从小到大递增循环。

为什么二者只有这个不同点？我不到啊

多重背包

二进制优化
思路：
将每种物品的s个分割成2的指数相互组合
$1,2,4,8,16……,2{k},c$，$且2<s,2{k+1}>s$，$1$~$2$可组合覆盖$1$~$2{k+1}-1$，有$c<2$使得$2^{k+1}-1+c = s$实现s的拆分

n种物品，每个s[i]个，全部组合成个数为$\log{s}$的小组合体（新的物品，拥有新的价值和体积），将这些小组合体进行0-1背包求解。

int cnt = 0;
//拆分

for(int i = 1;i <= n;i ++ )
{
	int a, b, s;           //a是物品体积 b是物品价值 s是物品个数
	cin >> a >> b >> s;
	int k = 1;
	while(k <= s)
	{
		cnt ++;
		v[cnt] = a * k;
		w[cnt] = b * k;
		s -= k;
		k *= 2;
	}
	if(s > 0)
	{
		cnt ++;
		v[cnt] = a * s;
		w[cnt] = b * s;
	}
}
n = cnt;
//0-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]);


cout<<f[m]<<endl;