背包问题之零一背包

注:参考文献《背包九讲》.

零一背包问题

一:题目描述

　　有 N 件物品和一个容量为 V 的背包.放入第 i 件物品耗用的费用为C_i(即所占用背包的体积),得到的价值是 W_i.求将哪些物品装入背包所得到的总价值最大.

二:基本思路

　　01背包是最基础的背包问题,这道题的特点是每种物品仅有一件,可以选择放或不放,且不要求背包必须被放满,只要求最后的总价值最大.

　　用子问题定义状态:F[i][v] 表示对于前 i 件物品,当背包容量为 v 时所能得到的价值最大值.设想,将 "前 i 件物品放入容量为 v 的背包中" 这个子问题,若只考虑第 i 件物品的策略(要么放要么不放),那么就可以转化为一个之和前 i - 1 件物品相关的问题.如果不放第 i 件物品, 那么问题就转化为 ”前 i - 1 件物品放入容量为 v 的背包中“,价值就是 F[i - 1][v]; 如果放第 i 件物品,那么问题就转化为 ”前 i - 1 件物品放入剩下的容量为 v - C_i 的背包中”, 此时获得的价值为 F[i - 1][v - C_i] + W_i。特殊的，当 v < C_i 时，可以认为当前的容量是放不下第 i 件物品的，即此时相当于不放第 i 件物品的价值F[i - 1][v].分析到这里则可得状态转移方程为:

　　　　　　　　　　　　　　　　F[i][v] = v < C_i? F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C_i] + W_i).

在这里要特别的说明一下,这个方程非常重要,一定要知道这是怎么推出来的,几乎后面的所有的背包问题都和这个方程有着密不可分的联系.

伪代码如下:

F[0...N][0...V] <--- 0

for i <--- 1 to N

　　for v <--- C_ito V

　　　　F[i][v] = v < C_i? F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C_i] + W_i);

具体代码:

1 void _01Pack(int F[][MAXV], int N, int V, int C[], int W[]){
2     memset(F, 0, sizeof(F));
3     for(int i = 1; i <= N; i++) {
4         for(int v = 0; v <= V; v++) {
5             F[i][v] = v < C[i] ? F[i - 1][v] : max(F[i - 1][v], F[i - 1][v - C[i]] + W[i]); //放或者不放两者之中选择最优者
6         }
7     }
8 }

三:优化空间复杂度

　　可以清楚的看到上面算法的时间复杂度和空间复杂度均为 O(N * V), 这里时间复杂度已经不能得到优化,但是空间复杂度确可以优化到 O(V).

　　先看上面代码是如何实现的.最外面一层循环,每次计算出二维数组 F[i][0...V] 的值,计算的时候 F[i][0...V] 是由它的上一层 F[i - 1][0...V] 而得到的.那么如果把这个数组换成一维的 F[v] 那么还能保留上一次的状态吗.答案是可以的.由于动态规划算法的无后效性,第 i + 1 件物品的选择与否不会影响到第 i 件物品(即它的前一件物品)的选择状态.那么可以在上面第二次循环中按照 v <--- V...0 递减的顺序来计算 F[v], 这样计算 F[v] 时所需要的状态 F[v] 和 F[v - C_i] + W_i仍然还是上一次的状态.而计算 F[v] 之后, v 的顺序是递减的, F[v] 不会影响到 F[v'] (v' < v), 因为F[v'] 只与 F[v'](上一次的值) 和 F[v - C_i] 有关, 而 F[v] > F[v'] > F[v' - C_i]. 所以又可得状态转移方程.

　　　　　　　　　　　　　　　　F[v] = max( F[v], F[v - C_i] + W_i).

伪代码如下:

F[0...V] <--- 0

for i <--- 1 to N

　　for v <--- V to C_i

　　　　F[v] = max( F[v], F[v - C_i] + W_i);

具体代码:

1 void _01Pack(int F[], int N, int V, int C[], int W[]){
2     memset(F, 0, sizeof(F));
3     for(int i = 1; i <= N; i++) {
4         for(int v = V; v >= C[i]; v--) {
5             F[i][v] = max(F[v], F[v - C[i]] + W[i]);
6         }
7     }
8 }

可以看到从第一个状态转移方程到第二个状态转移方程的空间优化效率还是挺大的:

　　　　　　F[i][v] = max( F[i - 1][v], F[i - 1][v - C_i] + W_i). ----> F[v] = max( F[v], F[v - C_i] + W_i).

在第二个方程中 F[v]¹ = max(F[v]², F[v - C_i] + W_i), 其实 F[v]²就相当与方程一中的 F[i - 1][v], 对应的 F[v - C_i] + W_i 就相当于 F[i -1][v - C_i] + W_i.这一正确性是在内层循环递减的前提下才成立的.否则, 将内层循环改为递增, 那么 F[i][v] 其实是由 F[i][v] 和 F[i][v - C_i] 推出来的,这不符合基本思路中的探讨.

之前说过由于 01背包的特殊性,这里将 01背包抽象化,方便之后的调用.

解决单个物品 01背包的伪代码:

def ZeroOnePack (F, C, W)

　　for v <--- V to C

　　　　F[v] = max( F[v], F[v - C] + W );

这么写之后, 01背包总问题解决的伪代码就可以改写成:

F[0...V] <--- 0

for i <--- 1 to N

　　ZeroOnePack(F, C[i], W[i]);

具体代码:

 1 const int MAXN = 10000;
 2 int N, V, C[MAXN], W[MAXN];
 3 
 4 void ZeroOnePack(int F[], int C, int W) { // 对于单个物品的决策
 5     for(int v = V; v >= C; v--) {
 6         F[v] = max(F[v], F[v- C] + W);
 7     }
 8 }
 9 
10 void solv(int F[]) {
11     memset(F, 0, sizeof(F));
12     for(int i = 1; i <= V; i++) {
13         ZeroOnePack(F, C[i], W[i]);
14     }
15 }

四: 01背包问题的拓展 ------ 初始化的细节问题

　　在上述 01背包的问题中,仅问得是 “如何选取,才能使的最后的总价值最大”, 这里并没有规定是否必须装满背包, 但是有的题将会给予这个附加条件, 即“在要求恰好装满背包的前提下, 如何选取物品, 才能使的最后的总价值最大 ”.

　　这两种问法, 在代码实现上相差无几.如果是上述问法,要求 “恰好装满背包”, 那么在初始化时除了将 F[0] 赋值为 0 之外, 其他的 F[1...V] 都应该赋值为 -∞

,这样就可以保证最后的得到的 F[V] 是一种恰好装满背包的最优解.如果没有要求必须把背包装满,而是只希望价值尽量最大,初始化时应该将 F[0...V] 全部设置为 0.

　　之所以可以这么做,是因为初始化的 F[] 事实就是没有任何物品放入背包时的合法状态.如果要求背包恰好装满,那么只有容量为 0 的背包在什么也不装且价值为 0 的情况下被装 "恰好装满",其他容量的背包如果不装物品, 那么默认的情况下都是不合法状态,应该被赋值为 -∞, 即对于第一个物品而言, 其合法状态只能由 F[0] 转移得到.如果背包并非必须被装满,那么任何容量的背包在没有物品可装时都存在一个合法解,即什么都不装,且这个解的价值为 0.所以将其全部初始化为 0 是可以的.

　　注:这个技巧完全可以拓展到其他背包问题中.

伪代码:

def ZeroOnePack (F, C, W)

　　for v <--- V to C

　　　　F[v] = max( F[v], F[v - C] + W )

end def

def slov()

　　F[0] = 0, F[1...V] <--- -∞

　　for i <--- 1 to N

　　　　ZeroOnePack(F, C[i], W[i])

end def

具体代码:

 1 const int MAXN = 10000;
 2 int N, V, C[MAXN], W[MAXN];
 3 
 4 void ZeroOnePack(int F[], int C, int W) {
 5     for(int v = V; v >= C; v--) {
 6         F[v] = max(F[v], F[v- C] + W);
 7     }
 8 }
 9 
10 void solv(int F[]) {
11     F[0] = 0;
12     for(int i = 1; i <= V; i++) F[i] = INT_MIN; // 除F[0] = 0之外, 其他全部赋值为负无穷
13     for(int i = 1; i <= V; i++) {
14         ZeroOnePack(F, C[i], W[i]);
15     }
16 }

五:一个常数级别的优化

上述伪代码的:

for i <--- 1 to N

　　for v <--- V to C_i

可以优化为:

for i <--- 1 to N

　　for v <--- V to max( V - SUM_(i...N)C_i, C_i)