浅谈背包问题

问题原型：

? 有一个背包，总体积为V，现有N个物品，每个物品都有一个体积Vi与价值Wi，问如何选择物品，使得在总体积不超过V的前提下价值最大。

类型1：0/1背包

限制条件:每个物品只有一个

朴素做法：

? 经典的动态规划问题，设置$$F(i,j)$$为遍历到第i个物品，包内体积为j能获得的最大价值。

? 那么对于每个物品，可以选也可以不选。

? 所以则有：$$F(i,j) = max(F(i-1,j),F(i-1,j-v[i])+w[i]) $$

优化：

? 1.滚动数组：

? 我们发现，$$F(i)$$只能从$$F(i-1)$$转移，我们可以利用滚动数组来优化空间复杂度。

? 即 $$F(i%2,j) = max(F((i-1)%2,j),F((i-1)%2,j-v[i])+w[i]))$$

? 可将空间复杂度从NV降低至V

? 2.优化枚举顺序与状态设置：

? 我们可设置一个新的状态：dp(i) ,表示体积为i时的最大价值

? 那么则有：$$dp(j) = max(dp(j),dp(j-v[i])+w[i])$$

? 而对于枚举顺序，我们发现：

? 若仍是正序枚举体积，则有可能调用到已选完物品$$i$$的状态，不符合0/1背包的性质。

? 所以为

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

? 这样，我们也可以把空间复杂度降为V级别

类型2：完全背包

限制条件：每种物品无限多个

朴素做法：

? 虽然物品有无限多个，但对于每个物品，他能被选择的次数不会超过$$\frac{V}{Vi}$$ 次，转成0/1背包，时间复杂度为$$O(V*\sum_{i=1}^n\frac{V}{Vi})$$

优化:

? 在0/1背包的第二种优化中，我们为了避免一个物品被重复选择，选择了倒序枚举，而在完全背包中，物品可被多次选择，所以可以直接正向枚举。时间复杂度为$$O(V*N)$$

类型3：多重背包

限制条件：物品$$i$$的数量为$$Ci$$

朴素做法：

? 将多个相同物品视为不同物品，再做0/1背包，总时间复杂度为$$O(V*\sum_{i=1}^nCi)$$

优化：

? 对于每个Ci，进行二进制分组。即每个物品分为若干种$$2^k$$个物品的和。由于二进制的性质，分组后可表示0到Ci的所有数字。时间复杂度为$$O(V*\sum_{i=1}^n\log Ci)$$

类型4：分组背包

限制条件：给定N组物品，其中第i组有Ci个物品，每组只能选择一种物品。

朴素做法：

? 将最外行枚举物品改为枚举组别

优化：

? 压缩状态的第一维，即：

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

浅谈背包问题

原文：https://www.cnblogs.com/Marcelo/p/13973236.html