题意概要:有个物品和一个容量为的背包,每个物品有重量和价值两种属性,要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
0-1背包
每个物品对应只有取和不取两种状态,对应0和1,并且每种物品只能取一次。
假设我们要求的价值函数为,含义为背包容量为时,放入第k个物品时的总价值,显然我们最终希望得到的最大值。
考虑状态的转移。
当第k个要放入的物品的重量超过容量时,那么就不放入,保持不变;如果可以放入时,考虑剩余容量为时的价值加上放入物品的价值即可。
简单的写法是外层循环,内层循环。
由于转移的过程只受影响,因此可以将二维降成一维。
for(int i = 1; i <= n; i++){
for(int j = C; j >= w[i]; j--){ //注意这行
C[j] = max(C[j], C[j - w[i]] + p[i]);
}
}
第2行不能被写成正向循环,为什么?因为0-1背包要求每个物品只能被取一次,如果写成正向循环,的值可以被多次改变,意味着物品可以被多次放进背包,这是不符合0-1背包要求的。反向循环就可以解决这个问题,每次更新均保证不会导致已更新的值再更新。
对于这个写法,空间的需求为。
完全背包
我第一次接触到的应该是完全背包,但是题目上也没有指明,所以和0-1背包搞混了。
完全背包和0-1背包的区别只有物品是否可以重复被选取。
这样我们的循环就应该写成正向循环:
for(int i = 1; i <= n; i++){
for(int j = 0; j <= C - w[i]; j--){
C[j + w[i]] = max(C[j + w[i]], C[j] + p[i]);
}
}