常见背包问题解法分析

导语：

背包问题可以说是一个老生常谈的问题，通常被用作面试题来考查面试者对动归的理解，我们经常说学算法，初学者最难理解的就是 “二归”，一个叫递归，另一个叫动归。背包问题属于特殊的一类动归问题，也就是按值动归，这篇文章我会列举一些常见的背包问题，涵盖 0-1 背包，完全背包，以及 多重背包。我同时会分享一些经典的题目帮助理解其中的思路与解题技巧。本文是参考了网上广为人知的 “背包九讲” 一书，文末会有下载链接。

初识背包问题

通常背包这一类题目，题目大概就是给你一个容量或者大小固定的背包，然后要求你去用这个背包去装物品，一般来说这些物品都是大小固定的，但是题目对物品的限定不同，衍生出来多种背包问题，例如 0-1 背包 问题中，物品个数有且仅有一个；完全背包 问题中的物品个数是无限的；多重背包 问题中的针对不同的物品，个数不一样。通常题目会要你求出背包能装的最大价值（每个物品都会有容量和价值），当然也会有不一样的问法，类似背包能否被装满，还有背包能装的最大容量是多少，多少种方式填满背包。但是这些并不是背包问题的所有，还有 分组背包 问题，依赖背包 问题等等，因为考虑到这篇文章主要是针对面试，而不是竞赛，这些有机会再去介绍。

0-1 背包

题目：

有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是C[i] ,得到的价值是W[i]。求解将哪些物品装入背包可使价值总和最大。求出最大总价值

分析：

对于每一个物品可以考虑放，或者不放；如果当前是第 i 个物品，当前背包里面物品总价值是，背包当前容量是 ，如果取这个物品，背包总价值会变成，背包容量会变成。之前我们提到过，背包是属于按值动归，我们把背包划分为 1-V 个区间，也就是背包所有可能的大小，然后针对所有的物品，看看每个背包容量下能存放的最大价值，代码如下：

public static int zeroOnePack(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;

    // dp[i][j]: 对于下标为 0～i 的物品，背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];
    
    // 背包空的情况下，价值为 0
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不选物品 i 的话，当前价值就是取到前一个物品的最大价值，也就是 dp[i - 1][j]
            dp[i][j] = dp[i - 1][j];
            
            // 如果选择物品 i 使得当前价值相对不选更大，那就选取 i，更新当前最大价值
            if ((j >= C[i - 1]) && (dp[i][j] < dp[i - 1][j - C[i - 1]] + W[i - 1])) {
                dp[i][j] = dp[i - 1][j - C[i - 1]] + W[i - 1];
            }
        }
    }
    
    // 返回，对于所有物品（0～N），背包容量为 V 时的最大价值
    return dp[n][V];
}

优化：

空间优化：

仅仅看代码就可以发现，其实 dp 数组当前行的计算只用到了前一行，我们可以利用 滚动数组 来优化，但是再仔细看下去的话，你就会发现其实还可以更优，当前行的遍历用到的值是上一行的前面列的值，如果我们第二层 for 循环遍历的时候倒着遍历的话，保证了前面更新的值不会被新计算的值覆盖掉，我们仅仅用一维数组就可以完美解决问题，代码如下：

public static int zeroOnePackOpt(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;

    int[] dp = new int[V + 1];
    
    // 背包空的情况下，价值为 0
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= C[i]; --j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }
    
    return dp[V];
}

极端情况优化：

当背包的 V 特别大的时候，对于每一个物品都去遍历一遍没有意义，通过阈值来进行优化，优化的同时可以考虑将数组从大到小排个序：

public static int zeroOnePackOpt(int V, int[] C, int[] W) {
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;
    
    int[] dp = new int[V + 1];
    
    int bound, sum = 0, total = 0;
    for (int i : C) {
        total += i;
    }

    for (int i = 0; i < n; ++i) {
        bound = Math.max(V - total + sum, C[i]);
        sum += C[i];
        for (int j = V; j >= bound; --j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }

    return dp[V];
}

0-1 背包 基本概况就是这些，当然可能问题的问法会不一样，例如：

• 背包能不能被装满
  

  解题思路就是将 int 数组换成 boolean 数组，也不用去考虑物品的价值来，直接看容量够不够，能不能装进背包即可

• 背包能装的最大容量
  

  也很简单，解法和上面 “背包能不能被装满” 一样，只不过最后需要从后往前遍历 dp 数组，直到找到 true

• 多少种方式塞满背包
  

  同样是不用考虑物品的价值，用 int 数组，但是里面记录的是个数，背包被填充的个数，也就是把这里的个数当作价值来看待，只不过 W[i] = 1。

下面是之前做过的一些关于 0-1 背包 的题目，我会给出相应的思路，可以试着写写，希望对你有帮助：

一、Need A offer
Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless 估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。

第一题思路：
0-1 背包 基础问题，这里背包大小就是 n 万美元，物品就是 m 所学校，申请费 a 是物品的容量，可能性 b 是物品的价值。但是有一点需要注意的是计算可能性的时候，不能仅仅取最大值，正确的方法应该是

二、饭卡
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

第二题思路：
背包大小是卡里面的余额，物品大小就是菜的价格。从 “每种菜可购买一次” 看出这其实是一个 0-1 背包 问题，这里比较诡异的一点是，背包容量可以超，但是仅限于最后一个物品。于是这里有一个思路上的变迁就是如何把这个诡异的背包问题变成正常的背包问题，如果能想到的话，其实不难，就是用 5 块钱去买最贵的那道菜，然后 “卡上余额 - 5” 作为背包的容量，其余的菜作为物品，然后这道题的问法就是 “背包能装的最大容量是多少”，最后的答案是 “（5 - 最贵的菜） + （卡上总余额 - 5 - 该背包问题的解）”

你可以看得出来得是，这里花了很大得篇幅来将 0-1背包 问题，的确，0-1 背包 是最简单的背包问题，但是是其他背包问题的基础，这种解题思路，以及这里提到的一些写代码上面的优化技巧是可以在其他的背包问题上复用的。

完全背包

题目

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品 的费用是 C[i]，价值是 W[i]。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。求解这个最大价值

分析

和之前的 0-1 背包 不同的是，完全背包 中的物品可以任意取多少都行，如果对 0-1 背包 理解的话，这里在写代码的时候只需要做一点的改变，就是在决定取不取当前物品的时候，之前 0-1 背包 是和之前不考虑当前物品的子问题结果做对比和更新，而 完全背包 相反，是和考虑当前物品的子问题做对比，代码实现如下：

public static int completePack(int V, int[] C, int[] W) {
    // 防止无效输入
    if (V == 0 || C.length != W.length) {
        return 0;
    }

    int n = C.length;
    
    // dp[i][j]: 对于下标为 0～i 的物品，背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];
    
    // 背包空的情况下，价值为 0
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不取该物品
            dp[i][j] = dp[i - 1][j];
            
            // 取该物品，但是是在考虑过或者取过该物品的基础之上(dp[i][...])取
            // 0-1背包则是在还没有考虑过该物品的基础之上(dp[i - 1][...])取
            if ((j >= C[i - 1]) && (dp[i][j - C[i - 1]] + W[i - 1] > dp[i][j])) {
                dp[i][j] = dp[i][j - C[i - 1]] + W[i - 1];
            }
        }
    }
    
    // 返回，对于所有物品（0～N），背包容量为 V 时的最大价值
    return dp[n][V];
}

优化

空间和之前一样，也是可以优化到一维数组，但是这里要注意的是，完全背包 考虑的值不再是更新前的值了（dp[i - 1][...]），而是更新后的值（dp[i][...]）,因此这时我们的第二层 for 循环需要从前往后遍历，保证当前考虑的值都是更新过后的值，代码如下：

public static int completePackOpt(int V, int[] C, int[] W) {
    if (V == 0 || C.length != W.length) {
        return 0;
    }

    int n = C.length;
    int[] dp = new int[V + 1];
    for (int i = 0; i < n; ++i) {
        for (int j = C[i]; j <= V; ++j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }

    return dp[V];
}

对于 完全背包 问题，也会有不一样的问法，但是和 0-1背包 问题类似，可以参照前面的内容，这里不做赘述，这里还有一道关于 完全背包 的题目可以巩固练习：

Piggy-bank

Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid. But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!

解题思路：
最基本的 完全背包 问题，背包大小是存钱罐的重量减去猪的重量，也就是里面装的钱币的总重量，钱币就是物品，每种钱币可以有无数个，但是注意这里要求的是总价值的最小值。

多重背包

题目

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M[i] 件可用，每件耗费的 空间是 C[i]，价值是 W[i]。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。求解该价值

分析

如果仅仅是要解决问题的话，其实非常简单，我们可以把这个问题变成 0-1 背包 问题去做，我这里就直接套用 0-1 背包 优化的版本，代码如下：

public static int multiplePack1(int V, int[] C, int[] W, int[] M) {
    int n = C.length;
    int[] dp = new int[V + 1];

    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < M[i]; ++k) {
            // consider about zeroOnePack
            for (int j = V; j >= C[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
            }
        }
    }

    return dp[V];
}

优化

上面代码的时间复杂度是，就是我们其实对每个物品，不管相同与否，都遍历了一遍。优化的话，可以这样思考，如果某个物品的总重量（C[i] * M[i] > V），那我们其实就可以考虑使用 完全背包 了，这样的话，对于这个物品的计算时间上从之前的 V * M[i] 变成了 V，如果 M[i] 很大的话，时间上的节省还是很可观的；另外一个优化就是在做 0-1 背包 的时候，这里有一个物品拆分的小优化，利用的是二进制的思想，假如 M[i] = 16，按照之前的思路，做 0-1 背包 需要的时间是 16 * V，但是这里的 16 可以拆成，1 + 2 + 4 + 8 + 1，也就是说把这 16 个物品缩减成了 5 个物品，当然对应物品的价值等于分配的数量乘上单个物品的价值，这样遍历时间缩减为 5 * V，其实就是将之前时间中的 M 变成了 。这两个优化把时间复杂度降为 ，代码如下：

public static int multiplePackOpt(int V, int[] C, int[] W, int[] M) {
    int n = C.length;
    int[] dp = new int[V + 1];

    for (int i = 0; i < n; ++i) {
        // go completePack
        if (C[i] * M[i] >= V) {
            for (int j = C[i]; j <= V; ++j) {
                dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
            }
        } 
        // go zeroOnePack
        else {
            // 1, 2, 2^2, 2^3,..., 2^(k-1), M[i] - 2^k + 1
            int k = 1, tmp = M[i];
            while (k < tmp) {
                for (int j = V; j >= k * C[i]; --j) {
                    dp[j] = Math.max(dp[j], dp[j - k * C[i]] + k * W[i]);
                }
                tmp -= k;
                k *= 2;
            }

            for (int j = V; j >= tmp * C[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j - tmp * C[i]] + tmp * W[i]);
            }
        }
    }

    return dp[V];
}

你可以看到，对于 多重背包 问题，难点是在优化上面，该问题综合考虑了前面提到的 0-1 背包 问题和 完全背包 问题，这样的优化思路第一次看上去很陌生，但是写的多了就不奇怪了，其实就是数学上面拆分数字的小技巧，同时这里也有几道题想和你分享，希望能帮你巩固对背包问题的认识：

一、Coins

Whuacmers use coins. They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m. But he didn't know the exact price of the watch. You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

第一题思路：
基本的多重背包问题，但是参考之前在 0-1 背包 问题中讲到的变形问法 “背包能不能被装满”

二、Are You Busy

As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad. What's more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as "jobs". A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs). So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss's advice)?

第二题思路：
算是多重背包的变形题目，xiaoA 所有的时间就是背包的容量，有三种物品，第一种是必须至少选一件，第二种是必须最多选一件，第三种是随便怎么选都可以，每个物品也会有价值，价值就是成就感。这里遍历的顺序很重要，先是遍历必须至少选一件的情况，然后是随便选，最后是最多选一件的，要注意的是在后面两次（随便选，最多选一件）的遍历中，要明确当前的背包值是否选了至少选一件这一类中的物品。

以上便是我想要分享的所有背包问题，其实背包问题还是比较常见的一类动态规划问题，这样子的分类或许对理解题目，寻找突破口很有帮助，当然别忘了勤于练习，这里的分享是基于背包九讲这一书的，最后会有下载链接，还有，如果觉得我有讲的不到位的地方，欢迎指出，谢谢

背包九讲