背包问题原理及LeetCode实战（上）

前言：本文详细梳理了背包问题原理，LeetCode实战请见背包问题原理及LeetCode实战（下）。

零、概述

背包问题及其变形在笔试、面试中经常出现，欲解决此类问题，需要明确三种典型的基本背包问题，掌握其原理和代码逻辑，并通过LeetCode实战开拓思维。本文介绍了0-1背包问题、完全背包问题、多重背包问题以及几道LeetCode典型例题来拓展背包问题的使用场景，旨在让读者由浅入深地理解背包问题。
背包问题一般使用动态规划的思想来解答，典型的三种背包问题都可以使用二维动态规划来解决，能满足一般笔试的要求。在理解好二维动态规划的基础上，要掌握一维动态规划数组的逻辑与写法，这种方法在时间、空间复杂度上均优于二维的动态规划，在代码的处理上也比较简单。
动态规划的核心是找到边界（初始化）和状态转移方程，文章会从思路和代码两个层面来介绍。

一、0-1背包问题

1.1 问题描述：

有一个容量为 C 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品的数量只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。

1.2 逻辑与思路：

先思考大问题的子问题，如果对所有物品进行遍历，对每一件物品来说，只有选择和不选择两种情况，我们需要找到使最终结果最优的方案。
定义F[i][j]为前i+1个物品中，当最大背包容量为j时，背包能装载的最大价值。例如，F[0][3]表示只考虑第一个物品，如果背包的最大容量为3，那么能装的价值是多少，F[2][4]表示只考虑前三个物品，如果背包的最大容量为4，那么能装的价值是多少。这样以来，我们最终要的结果就是F[n-1][C]，其中n为物品的个数。
从i=0的情况开始考虑，F[0][j]表示的是只考虑第一件物品，背包容量为j时能装载的最大价值。显然，当j>=w[0]时，F[0][j]=v[0]，反之，F[0][j]=0。这就是动态规划的边界。
如果i>0呢？对于第i件物品，有装和不装两种选择。不装的话很简单，当前的F[i][j]就等于F[i-1][j]。如果装载上第i件物品的话，那么背包中就有w[i]的重量是属于这件物品的，其余的物品最多只能占用那剩余的j-w[i]的空间，所以，F[i][j]等于前i-1件物品占用j-w[i]空间的最大价值即F[i-1][j-w[i]]与当前物品价值v[i]之和。所以就得到了状态转移方程为：F[i][j]=max(F[i-1][j], F[i-1][j-w[i]]+v[i])。
如果前面的推导你似懂非懂，那么来看下面这个具体的例子：
假设物品的体积w[i]=[5,6,2,3,4]，物品的价值v[i]=[6,12,5,6,6]，背包容量C=10。那么可得F[i][j]的表格为：

这张表格是从第一行开始由左向右一行一行建立的。i=0的行是初始化的结果，当j>=w[0]即j>=5时，F[0][j]=v[0]=6。从i=1开始，F[i][j]就取决于上一行的结果了，也就是取决于F[i-1][j]（正上方的格子）和F[i-1][j-w[i]]（上一行的左侧）这两个位置的数字。

1.3 代码实现

首先，main()函数中给定了条件，包括物品的重量、价值，和背包容量(后面的代码都是使用的这个main()函数）。

int main()
{
    int weight[]={5,6,2,3,4},value[]={6,12,5,6,6};
    vector<int> w(weight,weight+5),v(value,value+5);
    int C = 10;
    bag_0_1(w,v,C);
}

函数的实现也比较简单，先对F[i][j]初始化第一行，然后根据遍历物品，根据状态转移函数计算。

int bag_0_1(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<vector<int> > F(len,vector<int>(C+1,0)); // 把F初始化为0，否则有的编译器通过不了；
    // 初始化F的第一行
    for(int j=0;j<=C;j++)
    {
        if(j>=w[0])
            F[0][j]=v[0];
    }
    // F[i][j]的 j 可以理解为当前背包最大容量为j;
    for(int i=1;i<len;i++)
    {
        for(int j=1;j<=C;j++)
        {
            if(j>=w[i])
                F[i][j]=max(F[i-1][j],F[i-1][j-w[i]]+v[i]);
            else
                F[i][j]=F[i-1][j];
            
        }
    }
    return F[len-1][C];
}

1.4 解法优化

在这个问题的处理中，尤其是通过前面的表格更容易发现，第i行的计算完全依赖于第i-1行的结果，与更前面的行没有任何关系。所以从这个角度，二维的数组完全可以用一维数组来替代。一维数组的内容随着外层迭代的进行而不断更新。
根据前面的表格来理解这个过程：已经计算出了第i-1行的数据，下一次迭代的过程其实就是对这C+1个数据依次更新的过程。这里要注意一点细节，就是更新的第j个数据取决于原有的这个位置上的数据和j-w[i]这个位置上的数据，我们要保证j-w[i]这个位置（在位置j的前面）不要被更新掉。所以这里的内层循环要选择逆序循环。

int bag_0_1_opt(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<int> F(C+1,0);
    for(int i=0;i<len;i++)
    {
        // j要逆序遍历，否则更新后的F[j]会影响后续计算
        for(int j=C;j>=w[i];j--)
        {
            F[j]=max(F[j],F[j-w[i]]+v[i]);
        }
    }
    return F[C];
}

优化后的算法主要减小了空间复杂度。

二、完全背包问题

2.1 问题描述

有一个容量为 C 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品的数量都有无限个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。

2.2 逻辑与思路

完全背包问题和0-1背包问题的不同点在于前者的物品可以选任意个，而后者物品个数只有一个。不同于0-1背包中物品具有的两种选择（放或不放），完全背包问题对每个物品的选择为不放或放n个。可以看到，完全背包问题与0-1背包问题的相同点众多，处理的思路也应该类似。那么如何处理“放n个”问题，n该怎样定义？
依旧定义F[i][j]为前i+1个物品中，当最大背包容量为j时，背包能装载的最大价值。首先确定动态规划的边界，当i=0时，F[0][j]表示只考虑第一件物品，容量为j的背包中能装载的最大价值。因为背包智能装一件物品，那么当然要尽可能多地装，所以F[0][j]=(j/w[0])*v[0]。
边界问题确定了，下面处理“不放或放n个”的问题。对于i>0的情况，同样地，如果选择不放第i件物品，那么此时的F[i][j]=F[i-1][j]。假如要在背包中放置k个物品i，那么其余的物品最多只能占用j-k*w[i]的空间。其中k的取值要满足j-k*w[i]>=0。所以状态转移方程为F[i][j]=max(F[i-1][j], F[i-1][j-k*w[i]]+k*v[i])，其中，j-k*w[i]>=0。

2.3 代码实现

在逻辑上，完全背包问题与0-1背包问题相同，差别主要是在初始化和转移方程的细节，具体代码如下：

int bag_com(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<vector<int> > F(len,vector<int>(C+1,0));
    // 确定动态规划的边界，初始化
    for(int j=0;j<=C;j++)
        F[0][j]=(j/w[0])*v[0];
    for (int i = 1; i < len; i++)
    {
        for (int j = w[i]; j <= C; j++)
        {    
            //状态转移方程的处理
            int k=j/w[i];
            F[i][j]=F[i-1][j];
            while(k)
            {
                F[i][j]=max(F[i][j],F[i-1][j-k*w[i]]+k*v[i]);
                k--;
            }  
        }
    }
    return F[len-1][C];
}

2.4 解法优化

在完全背包问题中，尤其是通过状态转移方程可以看出，第i行的数据仅依赖于前一行的数据，所以此问题依然可以使用一维数组来解决。
这里有一点特别值得注意，在0-1背包问题的解法优化中提到的“逆序循环”是为了防止旧位置上的结果被更新掉，而在完全背包问题则不然，因为旧位置上的结果可以被更新！可以这样理解：在第i次遍历中，如果第j个位置被更新了，也就代表那个位置的最优结果是包含若干个物品i的，后续再用到那个位置的话，也是在已经包含若干个物品i的结果中，再加若干个物品i，这是符合题意的。所以内层循环采用的是顺序循环。
代码如下：

int bag_com_opt(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<int> F(C+1,0);
    for (int i = 0; i < len; i++)
        for(int j=w[i];j<=C;j++)
        {
            F[j]=max(F[j],F[j-w[i]]+v[i]);
        }
    return F[C];
}

三、多重背包问题

多重背包问题在完全背包问题的基础上做了一点限制，即限制了每种物品最多可用的件数。0-1背包的求解方法已经学会了，现在把复杂问题简单化，对于可用物品件数为n的物品，我们把这n件物品视为不同的物品来扩展w[i]和v[i]，这样就把这类问题转化成了0-1背包问题，即可按前面的解法去解决。