初识背包问题之「 0-1 背包」

朱雀 2023-08-17 15:27 68阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | P.yh

来源 | 五分钟学算法

## 前言 ##

背包问题可以说是一个老生常谈的问题，通常被用作面试题来考查面试者对动归的理解，我们经常说学算法，初学者最难理解的就是 “二归”，一个叫递归，另一个叫动归。

而背包问题属于特殊的一类动归问题，也就是按值动归，这篇文章主要讲解 **0-1 背包** 问题，如果读者能看明白，那么弄懂后续的 **完全背包** 以及 **多重背包** 这两个知识点问题也是不大的。

通常背包这一类题目，题目大概就是给你一个容量或者大小固定的背包，然后要求你去用这个背包去装物品，一般来说这些物品都是大小固定的，但是题目对物品的限定不同，衍生出来多种背包问题。

*  **0-1 背包** 问题中，物品个数有且仅有一个；
 *  **完全背包** 问题中的物品个数是无限的；
 *  **多重背包** 问题中的针对不同的物品，个数不一样。

通常题目会要你求出背包能装的最大价值（每个物品都会有容量和价值），当然也会有不一样的问法，类似背包能否被装满，还有背包能装的最大容量是多少，多少种方式填满背包。

但是这些并不是背包问题的所有，还有 **分组背包** 问题，**依赖背包** 问题等等，因为考虑到这篇文章主要是针对面试，而不是竞赛，这些有机会再去介绍。

## 0-1 背包 ##

### 题目描述 ###

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

### 题目分析 ###

对于每一个物品可以考虑放，或者不放；如果当前是第 i 个物品，当前背包里面物品总价值是 **Wcurrent**，背包当前容量是 **Vcurrent** ，如果取这个物品，背包总价值会变成 **Wcurrent + W\[i\]** ，背包容量会变成 **Vcurrent \- C\[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。

![640?][640]

**有热门推荐?**

1.【程序员】

2.【GitHub】

3.【算法】

4.【数据结构】

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20230810/38e05010ea114633b140b89b863b8684.png
[640]: /images/20230810/d1c5eeafb6de4f47acdf3aa1b5e4dbdc.png
[640_wx_fmt_jpeg 1]: /images/20230810/3006cdd0b2464be69a81da0a6f138c72.png