阅读 1375

数据结构和算法面试题系列—背包问题总结

这个系列是我多年前找工作时对数据结构和算法总结,其中有基础部分,也有各大公司的经典的面试题,最早发布在CSDN。现整理为一个系列给需要的朋友参考,如有错误,欢迎指正。本系列完整代码地址在 这里

0 概述

背包问题包括0-1背包问题、完全背包问题、部分背包问题等多种变种。其中,最简单的是部分背包问题,它可以采用贪心法来解决,而其他几种背包问题往往需要动态规划来求解。本文主要来源于《背包问题九讲》,我选择了比较简单的0-1背包问题和完全背包问题进行汇总。同时给出实现代码,如有错误,请各位大虾指正。本文代码在 这里

1 部分背包问题

部分背包问题描述: 有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。注意这里不要求把物品整个装入,可以只装入一个物品的部分。

解法: 部分背包问题常采用贪心算法来解决,先对每件物品计算其每单位重量价值 v[i]/w[i],然后从具有最大单位价值的物品开始拿,然后拿第二大价值的物品,直到装满背包。按照这种贪心策略拿到的必然是价值总和最大,这个比较简单,实现代码就略去了。

2 0-1背包问题

0-1背包问题描述

有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是v[i]。求解将哪些物品装入背包可使价值总和最大。注意物品只能要么拿要么不拿,这也正是 0-1 的意义所在。可以把部分背包问题看作是拿金粉,而 0-1 背包问题则是拿金块,一个可分,一个不可分。

分析

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即 f[i][w] 表示前 i 件物品恰放入一个容量为 c 的背包可以获得的最大价值。则其状态转移方程便是:

f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]} 
复制代码

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:将前 i 件物品放入容量为 c 的背包中 这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前 i-1 件物品的问题。

  • 如果不放第 i 件物品,那么问题就转化为 前 i-1 件物品放入容量为 v 的背包中,价值为 f[i-1][c]
  • 如果放第i件物品,那么问题就转化为 前 i-1 件物品放入剩下的容量为 c-w[i] 的背包中,此时能获得的最大价值就是 f[i-1][c-w[i]]再加上通过放入第 i 件物品获得的价值 v[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为 O(CN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到 O(N)。 由于在计算 f[i][c] 的时候,我们只需要用到 f[i-1][c]f[i-1][c-w[i]],所以完全可以通过一维数组保存它们的值,这里用到的小技巧就是需要从 c=C...0 开始反推,这样就能保证在求 f[c] 的时候 f[c-w[i]] 保存的是 f[i-1][c-w[i]] 的值。注意,这里不能从 c=0...C 这样顺推,因为这样会导致 f[c-w[i]] 的值是 f[i][c-w[i]] 而不是 f[i-1][c-w[i]。这里可以优化下界,其实只需要从 c=C...w[i] 即可,可以避免不需要的计算。伪代码如下所示:

for i=0..N-1
    for c=C..w[i]
        f[c]=max{f[c],f[c-w[i]]+v[i]};
复制代码

最终实现代码如下:

int knap01(int N, int C, int w[], int v[])
{
    int *f = (int *)calloc(sizeof(int), C+1);
    int i, c;

    for (i = 0; i < N; i++) {
        for (c = C; c >= w[i]; c--) {
            f[c] = max(f[c], f[c-w[i]] + v[i]);
        }
        printf("%d: ", i+1);
        printIntArray(f, C+1); // 打印f数组
    }
    return f[C];
}
复制代码

测试结果如下,即在背包容量为 10 的时候装第1和第2个物品(索引从0开始),总重量为 4+5=9,最大价值为 5+6=11。

参数:
w = [3, 4, 5] //物品重量列表
v = [4, 5, 6] //物品价值列表
C = 10

结果(打印数组f,i为选择的物品索引,c为背包重量,值为背包物品价值):
         
i/c 0 1 2 3 4 5 6 7 8 9 10
 0: 0 0 0 4 4 4 4 4 4 4 4 
 1: 0 0 0 4 5 5 5 9 9 9 9 
 2: 0 0 0 4 5 6 6 9 10 11 11 

KNap01 max: 11
复制代码

初始化的细节问题

我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了 f[0] 为 0 其它 f[1..C] 均设为 -∞,这样就可以保证最终得到的 f[N] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 f[0..C] 全部设为0。

为什么呢?可以这样理解:初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可能被价值为 0 的东西 “恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是 -∞ 了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

3 完全背包问题

问题描述

有 N 种物品和一个容量为 C 的背包,每种物品都有无限件可用。第i种物品的重量是 w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大,物品不能只装部分。

基本思路

这个问题非常类似于0-1背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件...等很多种。如果仍然按照解01背包时的思路,令 f[i][c] 表示前 i 种物品恰放入一个容量为 c 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:

f[i][c] = max{f[i-1][c-k*w[i]]+ k*w[i]| 0<=k*w[i]<=c }
复制代码

这跟0-1背包问题一样有O(CN)个状态需要求解,但求解每个状态的时间已经不是常数了,求解状态 f[i][c] 的时间是 O(c/w[i]),总的复杂度可以认为是 O(CN*Σ(c/w[i])),是比较大的。实现代码如下:

/*
 * 完全背包问题
 */
int knapComplete(int N, int C, int w[], int v[])
{
    int *f = (int *)calloc(sizeof(int), C+1);
    int i, c, k;
    for (i = 0; i < N; i++) {
        for (c = C; c >= 0; c--) {
            for (k = 0; k <= c/w[i]; k++) {
                f[c] = max(f[c], f[c-k*w[i]] + k*v[i]);
            }
        }
        printf("%d: ", i+1);
        printIntArray(f, C+1);
    }
    return f[C];
}
复制代码

使用与0-1背包问题相同的例子,运行程序结果如下,最大价值为 13,即选取 2个重量3,1个重量4的物品,总价值最高,为 4*2 + 5 = 13

i/c: 0 1 2 3 4 5 6 7 8 9 10
0:   0 0 0 4 4 4 8 8 8 12 12 
1:   0 0 0 4 5 5 8 9 10 12 13 
2:   0 0 0 4 5 6 8 9 10 12 13 

KNapComplete max: 13
复制代码

转换为0-1背包问题

既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选 C/w[i] 件,于是可以把第 i 种物品转化为 C/w[i] 件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。

更高效的转化方法是:把第 i 种物品拆成重量为 w[i]*2^k、价值为 w[i]*2^k 的若干件物品,其中 k 满足 w[i]*2^k<=C。这是二进制的思想,因为不管最优策略选几件第 i 种物品,总可以表示成若干个 2^k 件物品的和。这样把每种物品拆成 O(log C/w[i]) 件物品,是一个很大的改进。但我们有更优的 O(CN) 的算法。

进一步优化—O(CN)解法

我们可以采用与0-1背包问题相反的顺序遍历,从而可以得到 O(CN) 的解法,伪代码如下:

for i=0..N-1
    for c=w[i]..C
        f[c]=max{f[c],f[c-w[i]]+v[i]};
复制代码

这个伪代码与0-1背包伪代码只是 C 的循环次序不同而已。0-1背包之所以要按照 v=V..0的逆序来循环。这是因为要保证第i次循环中的状态 f[i][c] 是由状态 f[i-1][c-w[i]] 递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果 f[i-1][c-w[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果 f[i][c-w[i]],所以就可以并且必须采用 c=w[i]..C 的顺序循环。这就是这个简单的程序为何成立的道理。实现代码如下:

/**
 * 完全背包问题-仿01背包解法
 */
int knapCompleteLike01(int N, int C, int w[], int v[])
{
    int *f = (int *)calloc(sizeof(int), C+1);
    int i, c;
    for (i = 0; i < N; i++) {
        for (c = w[i]; c <= C; c++) {
            f[c] = max(f[c], f[c-w[i]] + v[i]);
        }
        printf("%d: ", i+1);
        printIntArray(f, C+1);

    }
    return f[C];
}
复制代码

参考资料

关注下面的标签,发现更多相似文章
评论