[数据结构与算法]4种背包问题 简单明了 0/1背包 完全背包 多重背包 混合背包 二进制优化

0/1背包

0/1背包问题：背包容量为c，有n个物品，物品xi的重量为wi、价值为vi，选择哪些物品装入背包使价值最大。
之所以说是0/1背包，是因为每个物品只有一个，只能不选/选，对应0/1。物品可选的最大数量由min{1, c/wi}确定。

使用二维数组的递推式

dp(i, j)表示前i个物品选择性地装入容量为j的背包能取得的最大价值。
dp(i, j) = dp(i-1, j)，wi > j # 背包容量j小于wi，装不下物品xi
dp(i, j) = max{dp(i-1,j), dp(i-1, j-wi) + vi}，wi<=j #背包装的下物品xi，有两种选择，装xi/不装xi，选择能使价值更大的。
时间复杂度：O(nc)
空间复杂度：O(nc)
这个递推式需要使用二维数组，我们可以发现第i层的结果只与第i-1层有关。因此可以采用两个一维数组，或者一个一维数组且内循环逆序。
一维数组内循环正序一般是后面的状态与前面的最新状态有关
一维数组内循环逆序一般是后面的状态与上一回的旧状态有关

使用两个一维数组的递推式

cur = 0, next = 1
dp(next, j) = dp(cur, j), wi > j
dp(next, j) = max{dp(cur,j), dp(cur, j-wi) + vi}，wi<=j
对i循环一次后交换cur、next的值
时间复杂度：O(n*c)
空间复杂度：O( c )

使用一个一维数组的递推式

dp(j) = dp(j), wi > j
dp(j) = max{dp(j), dp(j-wi) + vi}, wi <=j

int[] dp = new int[c+1];
for (int i = 0; i < n; i++) {
	for (int j = c; j >= w[i]; j--) {
		dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
	}
}
dp[c]为结果

时间复杂度：O(n*c)
空间复杂度：O( c )

两种问法对初始值的影响

背包刚好装满：dp(0) = 0，其他的为负无穷。因为容量为0, 不能再装东西，相当于装满，价值为0,合法。其他的汝dp(1)，初始时我们无法确定是否有物品能使容量为1的背包装满，故为负无穷。
背包不要求装满：所以的都为0。不要求装满，故而什么都不装合法。

完全背包

完成背包：背包的容量为c，有n个物品，物品xi的重量为wi、价值为vi，每种物品的数量是无限的。在物品的重量和不超过c的前提下，选择物品使价值最大。
与0/1背包的不同点：0/1背包每种物品只有1个，完全背包每种物品的数量无限，可选0个、1个、…、c/wi个。完全背包物品可选的最大数量由 c/wi 确定。
比较好的解法是将完全背包转化为0/1背包，文章下面 二进制优化详解了转化过程。

多重背包

多重背包：背包的容量为c，有n个物品，物品xi的数量为ai、重量为wi、价值为vi。选择物品装入背包，在不超过背包容量下使价值最大。
与0/1背包、完全背包的不同还是在数量上，多重背包的可选的最大数量由 min{ai, c/wi}确定。
比较好的解法是将多重背包转化为0/1背包，文章下面 二进制优化详解了转化过程。

混合背包

混合背包：背包的容量为c，有n个物品，物品xi的重量为wi、价值为vi，但物品的数量有的是1个、无限个、有限个。选择物品装入背包，在不超过背包容量下使价值最大。明显可以看出是0/1背包、完全背包、多重背包的混合。解决方法也很简单。关键是确定每个物品可选的最大数量。

二进制优化

物品xi的数量为ai、重量为wi、价值为vi。物品xi可选的最大数量为 kBound = min{ai, c/wi}。
即物品xi可选0个、1个、…、kBound个。kBound很大时，kBound + 1种策略就很费时间。考虑将kBound 分为 1 + 2 + 4 + … + 2^(k-1) + (kBound - 2^k + 1) , kBound - 2^k + 1 > 0。之前的kBound+1种策略，可以通过1, 2, 4, …, 2^(k-1), kBound - 2^k + 1 这些数相互组合对应。
例如物品x2的数量为10、重量为3、价值为2 。10 = 1 + 2 + 4 + 3 。
物品x2拆分为
重量3、价值2的物品x22一个
重量6、价值4的物品x24一个
重量12、价值8的物品x28一个
重量9、价值6的物品x26一个
kBound + 1种策略的对应

通过这样拆分，物品的数量得以下降，时间效率就变高了
物品都被拆分为只有1个，故而问题变成了0/1背包问题。

int[] dp = new int[c+1];
for (int i = 0; i < n; i++){
	int amount = 0;
	if(物品只有1个){
		amount = Math.min(1, c/w[i]);
	} else if(物品有无限个){
		amount = c/w[i];
	} else { //物品有限个
		amount = Math.min(a[i], c/w[i]);
	}
	int k = 1;
	while(k<amount) {
		for (int j = c; j >= k*w[i]; j--){
			dp[j] = Math.max(dp[j], dp[j - k*w[i]] + k*v[i]);
		}
		amount-=k;
		k+=k;
	}
	for (int j = c; j >= amount*w[i]; j--){
		dp[j] = Math.max(dp[j], dp[j - amount*w[i]] + amount*v[i]);
	}	
}
dp[c]为答案