问题描述

一共有 N 件物品，第 i （i 从 0 开始）件物品的重量为 w[i]，价值为 v[i] 。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？

暴力递归

分析题目可知，对于某一件商品 i ，你只能做出两个选择：要，或者不要。那么我们用递归穷举所有情况，每一件商品都尝试要或者不要，最后选出最大的价值。容易得到下面代码：

//index-商品序号
//take-要或者不要
//capacity-剩余容量
int process1(const vector<int> &weight, const vector<int> &value, int index, bool take, int capacity)
{
    if(index >= weight.size() || capacity < 0) //序号大于商品数量或背包容量不足时,返回0
        return 0;
    if(take)//如果要此商品
    {
        if(weight[index] > capacity)//那么判断是否装得下该商品
            return 0;
        //capacity - weight[index],将该商品放入背包,容量减少
        int ret1 = process1(weight, value, index + 1, true , capacity - weight[index]);//要下一件商品
        int ret2 = process1(weight, value, index + 1, false, capacity - weight[index]);//不要下一件商品
        return value[index] + std::max(ret1, ret2);//返回本商品价值+后续的较大值
    }
    else//如果不要此商品
    {
        //无需消耗capacity
        int ret1 = process1(weight, value, index + 1, true , capacity);//要下一件商品
        int ret2 = process1(weight, value, index + 1, false, capacity);//不要下一件商品
        return std::max(ret1, ret2);//返回后续的较大值
    }
}

int knapSack1(vector<int> weight, vector<int> value, int capacity)
{
    if(weight.size() != value.size())
        return 0;
    //从序号0的货物开始尝试要或者不要
    return std::max(process1(weight, value, 0, true, capacity), process1(weight, value, 0, false, capacity));
}

注意基线条件 capacity < 0 ，也就是说 capacity 可以等于 0，因为可能出现重量为 0 但价值不为 0 的货物。

动态规划

int knapSack2(vector<int> weight, vector<int> value, int capacity)
{
    if(weight.size() != value.size())
        return 0;
    vector<vector<vector<int>>> dp;//dp[index][capacity][take]
    //先统一初始化表
    dp.resize(weight.size());
    for(int i = 0; i < weight.size(); i++)
    {
        dp[i].resize(capacity + 1);//注意+1！！！！
        for(int k = 0; k <= capacity; k++)
        {
            dp[i][k].resize(2);
            dp[i][k][0] = 0;
            dp[i][k][1] = 0;
        }
    }
    
    //特例初始化
    int s = weight.size();
    for(int i = 0; i <= capacity; i++)
    {
        if(weight[s-1] <= i)
            dp[s-1][i][1] = value[s-1];
        dp[s-1][i][0] = 0;
    }

    //依次打表
    for(int i = s - 2; i >= 0; i--)
    {
        for(int k = 0; k <= capacity; k++)
        {
            dp[i][k][0] = std::max(dp[i+1][k][1], dp[i+1][k][0]);
            if(weight[i] <= k)
                dp[i][k][1] = value[i] + std::max(dp[i+1][k-weight[i]][1], dp[i+1][k-weight[i]][0]);
        }
    }
    return std::max(dp[0][capacity][1], dp[0][capacity][0]);
}

第 19~26 的特例初始化是什么意思？由暴力递归中的递推表达式可知，当前 index 依赖于 index + 1，所以填表必须按 index 从后往前进行，因此我们需要先求出最后的 index 对应的表格值。最后的 index 即为 weight.size-1 ，如果我们要这个这个商品，则先判定剩余容量是否能够装下它，如果能，则直接将对应表格赋值为 value[s-1] ；如果不要则赋值为 0 。 这些操作其实都和递归函数里的操作相对应。

capacity 则是后面依赖前面的，所以打表必须按 capacity 从前往后打，故内层 for 循环是从 k = 0 开始的。

优化参数

上面的方法中我们使用了三个状态变量，导致填表操作有些繁琐。实际上，take 参数完全可以省略，它的存在只是为了帮助我们理解思路，反而复杂化了函数的递归流程。以下是优化 take 参数后的版本：

int process3(const vector<int> &weight, const vector<int> &value, int index, int capacity)
{
    if(index >= weight.size() || capacity < 0)//capacity可以为0
        return 0;
    int ret1 = process3(weight, value, index + 1, capacity);//不要此货物
    int ret2 = 0;
    if(weight[index] <= capacity)//当前容量够,才能要此货物
        ret2 = value[index] + process3(weight, value, index + 1, capacity - weight[index]);//要此货物
    return std::max(ret1 , ret2);
}
int knapSack3(vector<int> weight, vector<int> value, int capacity)
{
    if(weight.size() != value.size())
        return 0;
    return process3(weight, value, 0, capacity);
}

process3 将 process2 中的两个 if 分支进行了合并，有完全一样的效果，并大大简化了代码和流程。

动态规划-改进

根据 process3 很容易得出下面代码：

int knapSack4(vector<int> weight, vector<int> value, int capacity)
{
    vector<vector<int>> dp(weight.size(), vector<int>(capacity + 1, 0));
    int last = weight.size() - 1;
    
    //特例初始化
    for(int c = 0; c <= capacity; c++)
    {
        if(weight[last] <= c)
            dp[last][c] = value[last];
    }
    
    //依次打表
    for(int i = weight.size() - 2; i >= 0; i--)
    {
        for(int c = 0; c <= capacity; c++)
        {
            int ret1 = dp[i+1][c];
            int ret2 = 0;
            if(weight[i] <= c)
                ret2 = value[i] + dp[i+1][c-weight[i]];
            dp[i][c] = std::max(ret1, ret2);
        }
    }
    return dp[0][capacity];
}

另外，也可以不使用特例初始化，直接统一处理，但前提是每次填表时都必须检查基线条件，这在动态规划入门-机器人行走中已经说明。统一处理的代码如下：

//不做特例初始化，统一处理  
int help(int index, int capacity, int size, const vector<vector<int>> &dp)  
{  
    if(index >= size || capacity < 0)  
        return 0;  
    return dp[index][capacity];  
}  
int knapSack6(vector<int> weight, vector<int> value, int capacity)  
{  
    vector<vector<int>> dp(weight.size(), vector<int>(capacity + 1, 0));  
    for(int i = weight.size() - 1; i >= 0; i--)  
    {  
        for(int c = 0; c <= capacity; c++)  
        {  
            int ret1 = help(i+1, c, weight.size(), dp);  
            int ret2 = 0;  
            if(weight[i] <= c)  
                ret2 = value[i] + help(i+1, c-weight[i], weight.size(), dp);  
            dp[i][c] = std::max(ret1, ret2);  
        }  
    }  
    return dp[0][capacity];  
}

总结

• 这类从左往右且可以归为“要或不要”的题型，都能使用类似方法解决。
• 尽可能优化参数，减少参数数量。