【动态规划】（七）背包动态规划

背包问题是动态规划中最经典的问题之一，也是机试中最常出现的问题。背包问题大体可分为九种类型。

1 0-1背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

0-1 背包是最简单的背包问题，定义状态 $dp[i][curv]$ 表示将前 i 件物品放入体积为 curv 的背包所能获得的最大价值，其中 $(curv \leq V)$，对于第 i 件物品，只存在拿与不拿两种情况，如果不拿第 i 件物品，那么问题就转化为“前 i - 1 件物品放入容量为 curv 的背包中所能获得的最大价值”，于是价值为 $dp[i-1][curv]$；如果拿第 i 件物品，那么问题就转化为“前 i - 1 件物品放入剩下的容量为 curv - vi 的背包中所能获得的最大价值”，此时能获得的最大价值就是 $dp[i-1][curv-vi]$ 再加上通过放入第 i 件物品获得的价值 wi，因此状态转移方程如下：

1	dp[i][curv] = max(dp[i-1][curv], dp[i-1][curv-v[i]] + w[i]);

于是可以写出代码：

#include<iostream>
#include<vector>

using namespace std;

class solution {
public:
    int ZeroOnePack(vector<int>& volume, vector<int>& value, int n, int v)
    {
        vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
        for(int i = 1; i <= n; ++i)
        {
            for(int curv = 1; curv <= v; ++curv)
            {
                dp[i][curv] = dp[i-1][curv];
                if(curv >= volume[i-1])
                    dp[i][curv] = max(dp[i][curv], dp[i-1][curv - volume[i-1]] + value[i-1]);
            }
        }
        return dp[n][v];
    }
};

int main() {
    int n, v;
    cin >> n >> v;
    vector<int> volume(n);
    vector<int> value(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> volume[i] >> value[i];
    }
    solution ans;
    cout << ans.ZeroOnePack(volume, value, n, v) << endl;
    return 0;
}

因为状态 i 至于状态 i - 1 有关，因此可以使用一维数组优化：

class solution {
public:
    int ZeroOnePack(vector<int>& volume, vector<int>& value, int n, int v)
    {
        vector<int> dp(v + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            // 注意体积必须逆序遍历，否则就需要一个额外的数组来存储上一次的状态
            for(int curv = v; curv >= volume[i-1]; --curv)
            {
                dp[curv] = max(dp[curv], dp[curv - volume[i-1]] + value[i-1]);
            }
        }
        return dp[v];
    }
};

需要注意的是使用一维数组的话，遍历体积 curv 的时候要从大到小遍历，因为如果从小到大遍历，那么后面需要的 dp[curv - volume[i-1]] + value[i-1] 就不是第 i - 1 的状态了，而是更新过的第 i 次的状态。此外遍历体积 curv 只需要遍历到当前物品的体积 volume[i-1] 即可，因为背包体积比当前物品体积小的话，一定装不进去，状态不需要更新，沿用前一次的状态即可。

如果将题目的要求改为必须将背包装满所能获得的最大价值，只需要修改动态规划的边界条件即可。现在的边界条件是 dp 数组全部初始化为 0 ，因为题目没有要求全部装满，只要不超过就可以，所以对于任意体积的背包，初始时都不装物品，最大价值都是 0；当要求背包必须装满时，初始化动态数组 dp 只有 $dp[0][0] = 0$，这代表将体积为 0 的背包用一个体积为0 的物体装满获得的最大价值为 0，而其它情况都初始化为 INT_MIN ，这代表其他体积的背包还没有装满，不符合要求，所以获得的价值也不存在。

0-1 背包问题虽然简单，但后面几乎所有的背包问题都是 0-1 背包问题的变体，都要用到 0-1 背包的方法去解决，因此 0-1 背包是最重要的背包问题。

2 完全背包问题

AcWing03. 完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

完全背包问题与 0-1 背包非常相似，只是这一次每件物品可以无限次数使用，如果还按照求解 0-1 背包时的思路，定义状态 $dp[i][curv]$ 表示将前 i 种物品放入体积为 curv 的背包所能获得的最大价值，这时要求解的总状态数还是 NV 个，但求解每个状态时就不是 $O(1)$ 复杂度了，而是 $O(curv / vi)$ 的复杂度，因为一个物体最多可以放入 curv / vi 次。于是总复杂度就是：
$$
O(NV \times \sum{\frac{curv}{vi}} )
$$
是比较大的。因此我们要考虑对它进行一些优化，稍微试用一下贪心的思想，对于每件物品 i，如果有物品 j 比它的重量小，价值大，那么就不需要考虑物品 i 了，因为我们任何情况下都可将价值小费用高的 i 换成物美价廉的 j，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据会一件物品也去不掉。而且这个优化方案往往需要 $O(N^2)$ 的时间。

一个更好的优化方案是，首先将费用大于容量 V 的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，这个过程只需要 $O(V+N)$ 时间，但可能会需要额外的空间，比如借助哈希表。

一般来说，我们不需要用上面如此复杂的思路，但是经过这些推导可以加深对问题的理解。同时也说明了 0-1 背包的重要性，因为以上思路全都是基于 0-1 背包，针对完全背包问题进行优化的。

解决这个问题更直接的思路一般是转化为 0-1 背包问题，事实上大多数的背包问题都可以这样做，再一次说明了 0-1 背包有多重要。

具体思路是：因为每件物品 i 最多只能选 V / vi 件，因此我们可以把物品 i 拆分成 V / vi 件体积和价值完全一样的物品，然后就转化成了一个 0-1 背包问题。

这样的思路完全没有改进基本思路的时间复杂度，但这却给了我们将完全背包问题转化为 0-1 背包问题的基本思路：将一种物品拆成多件物品。

于是我们可以进一步优化，将物品 i 拆成体积为 $vi * 2^k$ ，价值为 $wi*2^k$ 的若干件物品，这里用了二进制的思想，因为不管最优策略选几件第 i 种物品，总可以表示成若干个$2^k$ 件物品的和。这样我们把物品拆成了 $O(logV / vi)$ 件物品，是一个很大的优化。

但还有更好的方法，和 0-1 背包问题一样的 $O(NV)$ 复杂度的方法。我们只需要把 0-1 背包问题的一维数组解法遍历体积 curv 的顺序从逆序改为正序即可。之前逆序遍历是因为每件物品只能选一次，所以第 i 件物品的状态必须从没有选择第 i 件物品的状态 i - 1 得来，而现在物品 i 可以选择多次，所以第 i 种物品的状态恰好需要从已选入第 i 种物品的子结果转移而来。

class solution {
public:
    int CompletePack(vector<int>& volume, vector<int>& value, int n, int v)
    {
        vector<int> dp(v + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            for(int curv = volume[i-1]; curv <= v; ++curv)
            {
                dp[curv] = max(dp[curv], dp[curv - volume[i-1]] + value[i-1]);
            }
        }
        return dp[v];
    }
};

上面的两种遍历顺序可以颠倒，这在特定数据量的情况下可以做出常数级别的优化。

完全背包问题也是一个简单问题，但往往简单问题才更需要深刻理解，因为复杂的问题也都只是简单问题的变体。

因为 0-1 背包和完全背包是两个最基础的背包问题，因此我们可以将这两个问题的求解方法抽象成两个函数，在之后更复杂的问题中，可能会转换成这两种问题，直接调用这两个函数即可：

void ZeroOnePack(vector<int>& dp, int volume, int value, int v)
{
    for(int curv = v; curv >= volume; --curv)
    {
        dp[curv] = max(dp[curv], dp[curv - volume] + value);
    }
}

void CompletePack(vector<int>& dp, int volume, int value, int v)
{
    for(int curv = volume; curv <= v; ++curv)
    {
        dp[curv] = max(dp[curv], dp[curv - volume] + value);
    }
}

3 多重背包问题

AcWing04. 多重背包问题 I

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

多重背包问题同样可以转化为 0-1 背包实现，只需要把物品 i 拆分成 si 件同样的物品即可，然后我们按照 0-1 背包的方法求解。因此对于每件物品，只需要增加一重循环，遍历物品数量，代表这个物品拿几次：

#include<iostream>
#include<vector>

using namespace std;

class solution {
public:
    int MultiPack(vector<int>& volume, vector<int>& value, vector<int>& amount, int n, int v)
    {
        vector<int> dp(v + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            // 因为是基于0-1背包，所以要逆序遍历
            for(int curv = v; curv >= volume[i-1]; --curv)
            {
                for(int s = 0; s <= amount[i-1] && curv >= s * volume[i-1]; ++s)
                    dp[curv] = max(dp[curv], dp[curv - s * volume[i-1]] + s * value[i-1]);
            }
        }
        return dp[v];
    }
};

int main() {
    int n, v;
    cin >> n >> v;
    vector<int> volume(n);
    vector<int> value(n);
    vector<int> amount(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> volume[i] >> value[i] >> amount[i];
    }
    solution ans;
    cout << ans.MultiPack(volume, value, amount, n, v) << endl;
    return 0;
}

AcWing05. 多重背包问题 II

问题相同，但数据范围变为：
0 < N ≤ 1000
0 < V ≤ 2000
0 < vi, wi, si ≤ 2000

数据量过大的时候，上面的方法将物品拆分成了 si 件，复杂度太高，于是可以借鉴之前的二进制优化，将物品拆分成 $O(logsi)$ 件，具体的做法是将物品 i 拆分成系数为 $1, 2, 4, … , 2^{k-1},si-2^k+1$ 的若干件物品，其中 $si-2^k+1$ 其实就是物品总数减去之前拆分的数量总和，这样可以保证所有拆分的物品的系数加起来等于物品 i 的数量 si。例如，物品 i 的数量为 13 件，那么就拆分成系数为 1，2，4，6 的四件物品，四件物品的体积和价值为物品 i 的体积和价值乘以对应的系数。然后再利用 0-1 背包求解。另外如果物品 i 的数量 si 使得 si * vi 大于了背包总容量 V，那么问题就转化成了一个完全背包问题，因为相当于物品 i 可以在不超过背包容量的前提下无限次使用。于是可以写出代码：

class solution {
public:
    void ZeroOnePack(vector<int>& dp, int volume, int value, int v)
    {
        for(int curv = v; curv >= volume; --curv)
        {
            dp[curv] = max(dp[curv], dp[curv - volume] + value);
        }
    }
    
    void CompletePack(vector<int>& dp, int volume, int value, int v)
    {
        for(int curv = volume; curv <= v; ++curv)
        {
            dp[curv] = max(dp[curv], dp[curv - volume] + value);
        }
    }
    
    int MultiPack(vector<int>& volume, vector<int>& value, vector<int>& amount, int n, int v)
    {
        vector<int> dp(v + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            if(volume[i-1] * amount[i-1] > v)
            {
                CompletePack(dp, volume[i-1], value[i-1], v);
            }
            else
            {
                int k = 1, s = amount[i-1];
                while(s - k >= 0)
                {
                    ZeroOnePack(dp, k * volume[i-1], k * value[i-1], v);
                    s -= k;
                    k *= 2;
                }
                ZeroOnePack(dp, s * volume[i-1], s * value[i-1], v);
            }
        }
        return dp[v];
    }
};

二进制拆分方法是求解多重背包问题的一般写法，时间复杂度较好并且不难理解。实际上多重背包问题也有 $O(NV)$ 的解法，利用了单调队列优化状态求解过程，但已经超出了常规算法的范畴，证明起来也比较困难，不在我们的讨论范围内。

4 混合背包问题

AcWing07. 混合背包问题

有 N 种物品和一个容量是 V 的背包。
物品一共有三类：

第一类物品只能用1次（01背包）；

第二类物品可以用无限次（完全背包）；

第三类物品最多只能用 sisi 次（多重背包）；

每种体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

输入第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi, wi, si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

si = −1 表示第 i 种物品只能用1次；

si = 0 表示第 i 种物品可以用无限次；

si > 0 表示第 i 种物品可以使用 si 次；

混合背包是较为困难的背包问题，但经过前面的推导，实际上只要对三类物品分别应用上面的三个过程就可以。之前的代码都是全部读取数据后再处理，但实际上不需要全部读取，每读一件物品就可以更新一次 dp 数组了。

#include<iostream>
#include<vector>

using namespace std;

class solution {
public:
    // 0-1 背包
    void ZeroOnePack(vector<int>& dp, int volume, int value, int total)
    {
        for(int curv = total; curv >= volume; --curv)
        {
            dp[curv] = max(dp[curv], dp[curv - volume] + value);
        }
    }
    // 完全背包
    void CompletePack(vector<int>& dp, int volume, int value, int total)
    {
        for(int curv = volume; curv <= total; ++curv)
        {
            dp[curv] = max(dp[curv], dp[curv - volume] + value);
        }
    }
    // 多重背包
    void MultiPack(vector<int>& dp, int volume, int value, int amount, int total)
    {
        if(amount * volume > total)
        {
            CompletePack(dp, volume, value, total);
        }
        else
        {
            int k = 1;
            while(amount - k >= 0)
            {
                ZeroOnePack(dp, k * volume, k * value, total);
                amount -= k;
                k *= 2;
            }
            ZeroOnePack(dp, amount * volume, amount * value, total);
        }
    }
};

int main()
{
    int n,v;
    cin >> n >> v;
    // 不要求必须装满，所以初始化为0
    vector<int> dp(v + 1, 0);
    solution ans;
    for(int i = 0; i < n; ++i)
    {
        int volume, value, amount;
        cin >> volume >> value >> amount;
        if (amount < 0) ans.ZeroOnePack(dp, volume, value, v);
        else if (amount == 0) ans.CompletePack(dp, volume, value, v);
        else ans.MultiPack(dp, volume, value, amount, v);
    }
    cout << dp[v] << endl;
    return 0;
}

5 二维费用的背包问题

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价 1 和代价 2 ，第 i 件物品所需的两种代价分别为 a[i] 和 b[i]。两种代价可付出的最大值（两种背包容量）分别为 V 和 U。物品的价值为 value[i]。

这相当于在之前的基础上费用增加了一维，所以动态规划的状态也增加一维即可，于是原来的状态转移方程：

1	dp[i][curv] = max(dp[i-1][curv], dp[i-1][curv - volume[i]] + value[i]);

就可以改写为：

1	dp[i][cur_v][cur_u] = max(dp[i-1][cur_v][cur_u], dp[i-1][cur_v - a[i]][cur_u - b[i]] + value[i])

显然也可以不用三维数组，改用二维数组，当问题类似于 0-1 背包时，逆序遍历，类似于完全背包时，正序遍历，类似于多重背包时应用多重背包的解法。

当然，实际的题目中往往不会显式的告诉我们有两种代价，题目一般是这样描述的：

AcWing08. 二维费用的背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。

背包能承受的最大重量就相当于增加了一个代价——重量。于是我们就要同时考虑体积和重量两种代价。按照上面的思路，只要在 0-1 背包的基础上增加一重循环，遍历重量即可。

#include<iostream>
#include<vector>

using namespace std;

class solution {
public:
    void ZeroOnePack(
        vector<vector<int>>& dp, int volume, int weight, int value, int total_v, int total_w
    )
    {
        for(int cur_v = total_v; cur_v >= volume; --cur_v)
        {
            for(int cur_w = total_w; cur_w >= weight; --cur_w)
            {
                dp[cur_v][cur_w] = max(dp[cur_v][cur_w], dp[cur_v - volume][cur_w - weight] + value);
            }
        }
    }
};

int main()
{
    int n,v,m;
    cin >> n >> v >> m;
    vector<vector<int>> dp(v + 1, vector<int>(m + 1, 0));
    solution ans;
    for(int i = 0; i < n; ++i)
    {
        int volume, weight, value;
        cin >> volume >> weight >> value;
        ans.ZeroOnePack(dp, volume, weight, value, v, m);
    }
    cout << dp[v][m] <<endl;
    return 0;
}

6 分组背包问题

AcWing09. 分组背包问题

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

同样是 0-1 背包问题的变体，只是这次的一个物品变成了一组物品，相当于我们每次拿一个物品的时候，可以用同组内的其他物品替换。因此只要遍历所有组，更新 dp 状态，在更新时遍历组内每一个物品即可。

#include<iostream>
#include<vector>

using namespace std;

class solution {
public:
    void GroupPack(
        vector<int>& dp, int amount_in_group, vector<int>& volume, vector<int>& value, int total_v
    )
    {
        for(int cur_v = total_v; cur_v >= 0; --cur_v)
        {
            for(int cur_index = 0; cur_index < amount_in_group; ++cur_index)
            {
                if(cur_v >= volume[cur_index])
                    dp[cur_v] = max(dp[cur_v], dp[cur_v - volume[cur_index]] + value[cur_index]);
            }
        }
    }
};

int main()
{
    int n, v;
    cin >> n >> v;
    vector<int> dp(v + 1, 0);
    solution ans;
    for(int i = 0; i < n ; ++i)
    {
        int amount;
        cin >> amount;
        vector<int> volume(amount);
        vector<int> value(amount);
        for(int j = 0; j < amount; ++j)
        {
            cin >> volume[j] >> value[j];
        }
        ans.GroupPack(dp, amount, volume, value, v);
    }
    cout << dp[v] <<endl;
    return 0;
}

7 有依赖的背包问题

AcWing10. 有依赖的背包问题

背包问题的终极难度，对于机试、面试来说，属实没必要，碰到就算倒霉。

8 背包问题求方案数

AcWing11. 背包问题求方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最优选法的方案数。注意答案可能很大，请输出答案模 $10^9+7$ 的结果。

求解方案数一般都要用的动态规划状态之间的递加，主要思考如何递加。除了之前的记录最大价值的数组 dp 外，再定义一个记录达到最大价值的方案数的数组 cnt，因为是 0-1 背包问题，只有两种可能的情况：

选择当前物品得到的总价值比之前的价值高，即 dp[curv] < dp[curv-volume] + value，此时最大价值的方案数和之前一样，不会发生改变，相当于用当前物品替换之前的一件物品，即 cnt[curv] = cnt[curv - volume]
选择当前物品得到的总价值和之前的价值一样高，即 dp[curv] == dp[curv-volume] + value，这时达到最大价值的方案数增加了 cnt[curv - volume]，因为原本不超过 curv 的最大总价值方案数是 cnt[curv]，现在选择当前物品也可以达到这个最大价值，因此达到这个最大价值的方案总数就增加了 cnt[curv - volume] 种，即 cnt[curv] += cnt[curv - volume]

初始化 cnt 数组每一项都为 1，因为每一个体积都不装物品也至少是一种方案，最后编码时记得取模即可：

#include<iostream>
#include<vector>
#include<algorithm>
#include <climits>

using namespace std;

const int mod = 1e9 + 7;;

class solution {
    public:
    void ZeroOnePack(vector<int>& dp, vector<int>& cnt, int volume, int value, int total)
    {
        for(int curv = total; curv >= volume; --curv)
        {
            if(dp[curv] < dp[curv - volume] + value)
            {
                dp[curv] = dp[curv - volume] + value;
                cnt[curv] = cnt[curv - volume] % mod;
            }
            else if(dp[curv] == dp[curv - volume] + value)
            {
                cnt[curv] = (cnt[curv] + cnt[curv - volume]) % mod;
            }
        }
    }
};


int main()
{
    int n, v;
    cin >> n >> v;
    vector<int> dp(v + 1, 0);
    vector<int> cnt(v + 1, 1);
    solution ans;
    for(int i = 0; i < n; ++i)
    {
        int volume, value;
        cin >> volume >> value;
        ans.ZeroOnePack(dp, cnt, volume, value, v);
    }
    cout << cnt[v] % mod <<endl;
    return 0;
}

9 背包问题求具体方案

AcWing12. 背包问题求具体方案

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N

因为要保证字典序最小，那我们就要保证编号小的物品优先选到，也就是说，假设存在一个包含第 1 个物品的最优解，为了确保字典序最小那么我们必然要选该物品。那么问题就转化成从 2～N 这些物品中找到最优解。于是状态定义应该稍作修改，dp[i][curv] 表示从第 i 个物品到第 n 个物品总容量为 curv 的最大价值，于是状态转移也要相应的修改：

1	dp[i][curv] = max(dp[i+1][curv], dp[i+1][curv - volume[i]] + value[i]);

显然遍历物品的次序也要变为从后向前遍历。那么如何根据结果还原出路径呢？

我们拿着背包，即总体积 V，从第一个物品开始遍历，如果 dp[i][curv] == dp[i+1][curv - volume[i]] + value[i] ，说明选择了第 i 个物品，于是将 i 加入结果，总体积 V 减去物品 i 的体积，这样就可以还原出字典序最小的一个物品选取方案了。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, v;
    cin >> n >> v;
    vector<int> volume(n + 1);
    vector<int> value(n + 1);
    for(int i = 1; i <=n; ++i)
    {
        cin >> volume[i] >> value[i];
    }
    vector<vector<int>> dp(n + 2, vector<int>(v + 1, 0));
    for(int i = n; i > 0; --i)
    {
        for(int curv = 0; curv <= v; ++curv)
        {
            dp[i][curv] = dp[i+1][curv];
            if(curv >= volume[i])
                dp[i][curv] = max(dp[i][curv], dp[i+1][curv - volume[i]] + value[i]);
        }
    }
    int curv = v;
    for(int i = 1; i <= n; ++i)
    {
        if(curv - volume[i] >= 0 && dp[i][curv] == dp[i+1][curv - volume[i]] + value[i])
        {
            cout << i << " ";
            curv -= volume[i];
        }
    }
    return 0;
}

10 相关题目

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

完全背包问题，并且背包必须被装满。唯一的区别是，这次不是求最大价值，而是求最小数量，这相当于每个硬币的体积是 coins[i]，价值都是 1，求把背包装满的最小价值，只要把 max 改为 min 即可：

1	dp[curv] = min(dp[curv], dp[curv-coins[i]] + 1);

代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 要求装满，初始化只有dp[0] = 0
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int& c : coins)
        {
            // 完全背包，顺序遍历
            for(int curv = c; curv <= amount; ++curv)
            {
                if(dp[curv - c] != INT_MAX)	//防止越界
                    dp[curv] = min(dp[curv], dp[curv - c] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

经典的二维费用 0-1 背包，两种费用分别是 0 和 1 的最大数量，每个物品的价值都是 1，直接写出优化后的代码：

class Solution {
public:
    int calone(string s)
    {
        int ans = 0;
        for(auto& c: s)
        {
            if(c == '1') ++ans;
        }
        return ans;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(auto& s : strs)
        {
            int ones = calone(s);
            int zeros = s.size() - ones;
            for(int i = m; i >= zeros; --i)
            {
                for(int j = n; j >= ones; --j)
                {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0

题目的难点在于如何转化为背包问题，原问题相当于把石头分为两堆，使得两堆石头的差值最小，进一步可以转化为：如果所有石头的总重量是 sum，那么我们要把所有石头装入容量为 sum/2 的背包，并使背包内石头的总重量尽可能大，最终剩下的石头的最小重量就是 sum 减去两倍的背包内石头重量。这样转化的具体思路见详解为何能转换为背包问题。

转化后就是一个普通的 0-1 背包问题：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int total = sum / 2;
        vector<int> dp(sum + 1, 0);
        for(int i = 0; i < stones.size(); ++i)
        {
            for(int curv = total; curv >= stones[i]; --curv)
            {
                dp[curv] = max(dp[curv], dp[curv - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[total];
    }
};

分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

0-1 背包问题，并且要求把背包装满，这道题只问了是否可以，因此状态转移更简单：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 2 != 0) return false;
        int total = sum / 2;
        vector<bool> dp(total + 1, false);
        dp[0] = true;
        for(auto& x : nums)
        {
            for(int curv = total; curv >= x; --curv)
            {
                dp[curv] = dp[curv] || dp[curv - x];
            }
        }
        return dp[total];
    }
};

目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

问题可以转化为将数组中的数分为两组，且两组数字的和的差值为 target。假设数组中所有数字总和为 sum，那么问题等价于将数组中的数放入容量为 (sum+target)/2 的背包中，且必须装满的方案总数。于是就是一个简单的 0-1 背包求方案总数的问题。只要注意特殊情况的判断即可，如果 (sum+target)/2 不是整数则无法分配，如果 target 的绝对值比数组中所有数字的总和都大也无法分配。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int total = sum + target;
        if(abs(target) > sum || total % 2 != 0) return 0;
        total /= 2;
        vector<int> dp(total + 1, 0);
        dp[0] = 1;
        for(auto& x : nums)
        {
            for(int curv = total; curv >= x; --curv)
            {
                dp[curv] += dp[curv - x];
            }
        }
        return dp[total];
    }
};

零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

完全背包求方案数，且背包必须装满：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(auto& c : coins)
        {
            for(int curv = c; curv <= amount; ++curv)
            {
                dp[curv] += dp[curv - c];
            }
        }
        return dp[amount];
    }
};

组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

由于每个数字可以使用多次，因此这也是一个完全背包求方案数问题。与上面的完全背包求方案数问题稍有不同的是，这里不同顺序代表不同的组合，也就是物品的顺序不同也代表一种不同的方案，所以对于每一个当前容积的背包 curv，把背包装满的方案数等于所有 curv-x 的背包的方案数的总和，x 是每个体积小于 curv 的物品，即：

for(auto& x : nums)
{
    if(x <= curv) dp[curv] += dp[curv - x];
}

因此我们只需要改变完全背包原本的内外层遍历即可：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target + 1, 0);
        dp[0] = 1;
        for(int curv = 1; curv <= target; ++curv)
        {
            for(auto& x : nums)
            {
                if(curv >= x)
                {
                    dp[curv] += dp[curv - x];
                }
            }
        }
        return dp[target];
    }
};

盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称盈利计划。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以返回结果模 10^9 + 7 的值。

显然是一个二维费用的 0-1 背包问题，但第二个费用限制是至少产生 minProfit 的价值，与之前稍有不同，但总体思路还是完全一样的，注意对于至少产生 minProfit 的处理，非常巧妙：

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        int len = group.size(), MOD = (int)1e9 + 7;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = n; j >= members; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - members][max(0, k - earn)]) % MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
};