博客

1.什么叫01背包问题？

背包问题通俗的说，就是假如你面前有5块宝石分别为a, b, c, d, e，每块宝石的重量不同，并且每块宝石所带来的价值也不同（注意：这里宝石的重量的价值没有特定关系），目前我们有一个背包，只有固定的容量，要解决的问题就是在一定容量的背包面前装哪几块宝石才能获取到最大的价值，对于每块宝石我们只有拿或者不拿这两种选择，拿为1不拿为0，

因此叫做0-1背包问题

，下面通过一个例子来深入理解背包问题

2.01背包问题例子

假设a, b, c, d, e五块宝石的重量分别为为2， 2， 6， 5， 4，价值分别为6， 3， 5，4， 6 ，我们目前的背包可以装重量为10的物品，怎么装才能使得获取的价值最大？

首先对于我们人去操作而言，首先考虑应该是质量最轻，并且价值最大的，从数据中我们可以看到宝石a质量最小，且价值最大，应该优先考虑装这一块，然后依次考虑其他的。这种方式就是考虑性价比最高的宝石。我们可以将这个问题进行简化，目前是背包承重为10，因此我们的选择较多，不知从何下手，那么我们假设背包的承重为5或者是3甚至是2， 1。在这种情况下，我们的选择就不多了，对于人类选择也是，在选择不多的情况下更容易找出最优方案，同样计算机也是。因此我们的背包问题也是从这开始，将选择较多的问题转化为选择不多的问题。在选择不多的情况下进行选择，有利于比较判断，依次递增，最后解决背包承重为10的问题。

对于背包问题，其实是一个动态规划，对于动态规划，大多数都是用一个数组来进行保存，对于初学者而言，如果我直接给你个数组公式，相信你看着也不太懂公式表示什么，数组怎么来的，别着急，耐心看，下面就一步一步的解释该数组的数据是怎么来的，公式是怎么推导出来的，附代码

3. 步骤详解

首先我们假设背包承重为0

，当然一块宝石都不能装，同样假设背包承重为1，也是一块宝石都不能装。

接下来考虑承重为2的时候：

考虑宝石a，目前背包容量为2，装—价值为6，不装—-价值为0—->>选择装  价值为6， 容量为0

考虑宝石b，目前背包容量为0，装—（得空出2的容量，因此得拿出宝石a，放入宝石b）价值为3，不装—价值为6—->>选择不装，价值为6，容量为0

对于宝石c, d, e来说，承重为2的背包不足以装下其中任意一块宝石，不考虑，因此最终获得解决方案为，装宝石a，最大价值为6

难度升级，考虑背包承重为4（承重为3的时候，解决方案和承重为2的时思路一致，方案相同，不作叙述）

考虑宝石a，目前背包容量为4，装—价值为6，不装—价值为0—->>选择装

价值为6，容量为2

考虑宝石b，目前背包容量为2，装—（需要2的容量，足够）价值为6+3=9，不装—价值为6—->>

选择装，价值为9，容量为0

考虑宝石c，目前背包容量为0，装—（需要6的容量），不考虑

考虑宝石d，目前背包容量为0，装—（需要5的容量），不考虑

考虑宝石e，目前背包容量为0，装—（需要4的容量，取出宝石a和b，放入宝石e），价值为4—->>

选择不装，价值为9，容量为0

因此最终解决方案为装入a和b

根据我们的解题思路，大家可以看到，在考虑一块宝石需不需要装入背包的时候，是需要考虑装入背包时需要多少空间，而将背包腾出这么大的空间又要拿出价值多少的宝石，就是在放入宝石和拿出宝石之间做一个价值比对，从而进行选择。而我们之前存入的宝石及其价值就需要一个数组来进行存储

其中蓝色区域为我们需要的二维数组，填写顺序为从下到上，从左到右，以第一列为例，此时背包承重为1，依次考虑宝石e, d, c, b, a（这里相比上面分析相比是倒序的，方便表格的填写以及效果观看），当前的最大价值为0，当随着背包承重在增加，我们依照上述步骤进行分析

以背包承重为8进行分析（非常重要！！！！！！！）

考虑宝石e，目前背包容量为8，装—-价值为6，不装—-价值为0，选择装，因此表格8e对应为6

考虑宝石d，装—-需要5的空间，还剩余3的空间，因此查看在背包容量为3的时候，且只有e宝石，最大价值为0，加上d的价值为4，总价值为4，不装—–价值为6，因此不装，8d值为6

考虑宝石c，装—需要6的空间，还剩余2的空间，因此查看背包容量为2的之后，且只有宝石e和d，最大价值为0.加上c的价值为5，总价值为5，不装—–价值为6，因此不装，8c为6

考虑宝石b，装—需要2的空间，还剩余6的空间，因此查看背包容量为6时，只有宝石e、d和c，最大价值为6，加上b的价值为3，总价值为9，不装–价值为6，因此装，8b为9

考虑宝石a，装—需要2的空间，还剩余6的空间，因此查看背包容量为6时，只有宝石e、d、c和b，最大价值为6，加上a的价值为6，总价值为12，不装—价值为9，因此装，8a为12

在此处分析需要注意两点：

1. 需要预先给宝石排好顺序，依次考虑

2.表格填写顺序，需要先考虑背包容量小时，因为大容量背包需要用到小容量背包时的数据（数组要依次填充）

根据上述分析，我们来确定背包问题中的数学公式，假设每种宝石的重量分别为

，每块宝石的价值分别为

，其中i表示第i个宝石（也就是为什么要给宝石排序），假设二维数组为

,其中i表示前i个宝石存在的情况下，背包容量为j时能获取的最大价值，则

其中max函数中的第一项表示，不装第i个宝石的情况，第二项表示装第i个宝石，就需要考虑总背包容量减少w[i]，然后总价值加上当前v[i]。

4.代码如下

public int testPack(int[] weight, int[] value, int cap){
        if(cap == 0 || weight.length == 0){
            return 0;
        }
        int len = weight.length;
        int[][] f = new int[len][cap + 1];//cap+1因为给定容量为cap，因此j的循环必须到cap
        for(int j = 1; j < cap + 1; j++){
            for(int i = 0; i < len; i++){
                if(weight[i] > j){//如果当前宝石重量大于整个背包的承重
                    if(i == 0){//如果当前只考虑了第一块宝石
                        f[i][j] = 0;
                    }else {
                        f[i][j] = f[i - 1][j];
                    }
                }else{
                    if(i == 0){//如果当前只考虑了第一块宝石
                        f[i][j] = value[i];
                    }else {
                        f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]);
                    }
                }
            }
        }
        return f[len - 1][cap];
    }

    @Test
    public void test(){
        int[] weight = new int[] {2, 2, 6, 5, 4};
        int[] value = new int[] {6, 3, 5, 4, 6};
        int cap = 10;//可修改对应表格进行验证
        System.out.println(testPack(weight, value, cap));//输出为表格中对应数据
    }

希望对初学者有所帮助，欢迎批评指正