背书包的小新对背包问题的理解

雄关漫道真如铁，而今迈步从头越

@[toc]
动态规划的核心在于如何转移状态（这可真是个让人头秃得问题）

我们就从背包问题入门吧。

1.01背包问题

有N件物品和一个容量为V的背包。第 i件物品的费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路：每个物品只有一件，每件可以选择取或不取，运用闫氏dp法

状态表示： f[i][j]表示在前i个物品中选，体积不超过j的最大价值

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有两种选择，选或不选

不选：意味着从前i-1个物品中选一些物品且体积不大于j的最大价值，在状态计算中相当于f[i-1][j]
选：这意味着我必须选第i个物品，然后在前i-1个物品中选择一些物品且体积不大于j-v（因为我已经选上了第i个物品，第i个物品已经占据了v个体积）的最大价值在加上第i个物品的价值

状态转移方程：

不选：f[i][j] = f[i-1][j]
选： f[i][j] = f[i-1][j-v] + w

朴素版核心代码

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        if (j >= v[i])
            f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}

滚动数组优化代码

当枚举到第i个物品时，只会用到第i-1层的状态，所以我们可以利用奇偶变换的思路，可以讲转移数组f的第一维只用两个空间就可以了，当i是偶数时，相当于第0层，当i是奇数时，就相当于第1层，所以上一层就是与自己的奇偶性不同的那一层。

那如何判断奇偶性的，可以用数值的二进制的性质，第0位为1就是奇数，第1位为0就是奇数.

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        f[i & 1][j] = f[(i - 1) & 1][j];
        if (j >= v[i])
            f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
    }
}
cout << f[n & 1][m];

优化到一维代码

我们又可以想一下，能不能只用一维数组就可以实现状态转移？

我们可以进一步看出，枚举到第i个物品体积为j时，只会用到f[i-1][j-v]和f[i-1][j],我们可以发现，每次用到的f[i-1][j-v]都在j这一列的前面，而且f[i][j]=f[i-1][j],那我们是不是就可以优化成一维，但是枚举体积j时要从大到小，如果我们还是从小到大的话就会导致后面的体积j+v的状态会由j的这个状态转移，但是在体积j的状态已经发生了变化，而体积从大到小就不会产生这个问题。

for (int i = 1; i <= n; i++)
{
    for (int j = m; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);
}

2. 完全背包

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路：完全背包和01背包的不同点在于完全背包每个物品可以选无数次，而01背包就只能选一次

状态表示： f[i][j]表示在前i个物品中选，体积不超过j的最大价值

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有多种选择，分别是选0件、1件、2件...直到背包装不下为止

选0件：意味着从前i-1个物品中选一些物品且体积不大于j的最大价值，在状态计算中相当于f[i-1][j]
选k件：这意味着我必须选第i个物品k件，相当于第i个物品的体积扩大到k倍，价值也扩大w*k，然后在前i-1个物品中选择一些物品且体积不大于j-k*v的最大价值在加上第i个物品的价值

朴素版（可能会TLE）

朴素版的复杂度是n^3

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        for (int k = 0; k * v[i] <= j; k++)
        {
            f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i], f[i][j]);
        }
    }
}

优化

我们可以根据转移过程发现

f[i][j]     = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2 * v] + 2 * w....+ f[i - 1][j - k * v] + k * w);
f[i][j - v] = max(             f[i - 1][j - v],     f[i - 1][j - v] + w, ....      + f[i - 1][j - k * v] + (k-1) * w);

状态转移方程可以转化为

f[i][j] = max(f[i - 1][j], f[i][j - v] + w)

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        if (j >= v[i])
            f[i][j] = max(f[i][j - v[i]] + w[i], f[i][j]);
    }
}

一维优化

同学们可以发现这里一维优化和01背包的一维优化有什么不同，这里的j是从小到大枚举的，也就是说每次枚举到j的时候，是需要由前面已经发生变化的状态转移过来，01背包是不能由发生变化的状态转移过来，必须保证转移的时候，前一层状态没有发生变化。这也就是很多同学困扰在这里的原因，就是要搞清楚状态是由什么状态转移过来的。

for (int i = 1; i <= n; i++)
{
    for (int j = v[i]; j <= m; j++)
    {
        f[j] = max(f[j - v[i]] + w[i], f[j]);
    }
}

3. 多重背包问题

有N种物品和一个容量为V的背包。第i种物品最多有s[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路：多重背包的限制条件是每个物品只能选给定的次数，和完全背包、01背包又有所不同,只需要讲完全背包的代码改一改，物品个数限制到s[i]个

状态表示： f[i][j]表示在前i个物品中选，体积不超过j的最大价值

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有多种选择，分别是选0件、1件、2件...直到背包装不下为止

选0件：意味着从前i-1个物品中选一些物品且体积不大于j的最大价值，在状态计算中相当于f[i-1][j]
选k件：这意味着我必须选第i个物品k件，相当于第i个物品的体积扩大到k倍，价值也扩大w*k，然后在前i-1个物品中选择一些物品且体积不大于j-k*v的最大价值在加上第i个物品的价值

朴素版

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
        {
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
}

一维优化版

for (int i = 1; i <= n; i++)
{
    for (int j = m; j >= 0; j--)
    {
        for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
        {
            f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
        }
    }
}

二进制优化

时间复杂度O(nmlog(s))*

我们做完全背包和多重背包的时候，其实每个物品都可以看成是一个物品有多个，那么就可以讲完全背包和多重背包都转化为01背包，但这样复杂度太高，我们有什么方法可以解决这个问题呢？

我们想到了二进制拆分的方法，每个数都可以由1、2、4、8、16...s - 2^k-1相加得到，并且0-s的每一个数都可以由这些数的一些数相加得到，这样我们就可以讲s个物品转化为log(s)件物品，且每个物品都是独立的，不受其他物品影响。

举个例子：7可以由1、2、4得到，那么7个物品就可以由三个物品得到，而且结果是一样的。

for (int i = 1; i <= n; i++)
{
    int a, b, s;
    scanf("%d%d%d", &a, &b, &s); // a是体积，b是价值，s 是个数
    for (int num = 1; s; num <<= 1) // 二进制拆分，num为拆分后的每一件物品的数量
    {
        num = min(s, num);
        for (int j = V; j >= num * a; j--)
        {
            f[j] = max(f[j], f[j - num * a] + num * b);
        }
        s -= num;
    }
}

单调队列优化

时间复杂度O(mn)

这道题是背包问题和滑动窗口的结合，理解了滑动窗口这一题也就不难了

我们先来回顾一下传统的dp方程

dp[i][j] 表示将前 i 种物品放入容量为 j 的背包中所得到的最大价值
dp[i][j] = max(不放入物品 i，放入1个物品 i，放入2个物品 i, ... , 放入k个物品 i)
这里 k 要满足：k <= s, j - k*v >= 0

不放物品  i = dp[i-1][j]
放k个物品 i = dp[i-1][j - k*v] + k*w

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2*v] + 2*w,..., dp[i-1][j-k*v] + k*w)
实际上我们并不需要二维的dp数组，适当的调整循环条件，我们可以重复利用dp数组来保存上一轮的信息

我们令 dp[j] 表示容量为j的情况下，获得的最大价值
那么，针对每一类物品 i ，我们都更新一下 dp[m] --> dp[0] 的值，最后 dp[m] 就是一个全局最优值

dp[m] = max(dp[m], dp[m-v] + w, dp[m-2*v] + 2*w, dp[m-3*v] + 3*w, ...)

接下来，我们把 dp[0] --> dp[m] 写成下面这种形式
dp[0], dp[v],   dp[2*v],   dp[3*v],   ... , dp[k*v]
dp[1], dp[v+1], dp[2*v+1], dp[3*v+1], ... , dp[k*v+1]
dp[2], dp[v+2], dp[2*v+2], dp[3*v+2], ... , dp[k*v+2]
...;
dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j];

显而易见，m 一定等于 k*v + j，其中  0 <= j < v
所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的
也就是说，dp[k*v+j] 只依赖于 { dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] }

因为我们需要的是{ dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] } 中的最大值，
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题

所以，我们可以得到
dp[j]    =     dp[j]
dp[j+v]  = max(dp[j] +  w,  dp[j+v])
dp[j+2v] = max(dp[j] + 2w,  dp[j+v] +  w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w,  dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])
...
但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换

dp[j]    =     dp[j]
dp[j+v]  = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w
...
这样，每次入队的值是 j+k*v

单调队列问题，最重要的两点
1）维护队列元素的个数，如果不能继续入队，弹出队头元素
2）维护队列的单调性，即：尾值 >= dp[j + k*v] - k*w

本题中，队列中元素的个数应该为 s+1 个，即 0 -- s 个物品 i

感谢这位同学！！！
作者：lys
链接：https://www.acwing.com/solution/content/6500/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

for (int i = 1; i <= n; i++)
{
    int v, w, s;
    cin >> v >> w >> s;
    //注意这里为什么要g数组复制f数组，首先这里的j是从小到大更新的
    // 可能会用到已经更新过的状态
    // 比如说当v==1,时
    // f[4] = max(f[4],f[3]+w,f[2]+2w,f[1]+3w).
    // f[5] = max(f[5],f[4]+w,f[3]+2w,f[2]+3w,f[1]+4w)
    // 这里可以看到f[5]会由这一层的f[4]转移过来，f[4]可能已经被更新，所以不能使用f数组取更新现在的状态
    memcpy(g, f, sizeof f);
    for (int j = 0; j < v; j++)
    {
        int hh = 0, tt = -1;
        for (int k = j; k <= m; k += v)
        {
            while (hh <= tt && k - s * v > q[hh])
                hh++;
            while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
                tt--;
            q[++tt] = k;
            f[k] = g[q[hh]] + (k - q[hh]) / v * w;
        }
    }
}

4. 混合背包问题

有 NN 种物品和一个容量是 V 的背包。

物品一共有三类：

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

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

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

每种体积是 vi，价值是 wi。

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

基本思路：混合背包也就是01背包+完全背包+多重背包

直接上代码，具体前面已经讲过了

for (int i = 1; i <= n; i++)
{
    int v, w, s;
    cin >> v >> w >> s;
    if (s == -1)
    {
        for (int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }
    else if (s == 0)
    {
        for (int j = v; j <= m; j++)
            f[j] = max(f[j], f[j - v] + w);
    }
    else
    {
        for (int num = 1; s; num <<= 1)
        {
            num = min(s, num);
            for (int j = m; j >= num * v; j--)
            {
                f[j] = max(f[j], f[j - num * v] + num * w);
            }
            s -= num;
        }
    }
}

5.二维费用的背包问题

有 NN 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

基本思路：每个物品只有一件，每件可以选择取或不取，01背包中只有体积一个限制条件，而本题有两个条件体积和重量，其实也很简单，就是多增加了一维而已，和01背包的性质是一样的。

状态表示： f[i][j][k]表示在前i个物品中选，体积不超过j且重量不超过k的最大价值

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有两种选择，选或不选

不选：意味着从前i-1个物品中选一些物品且体积不大于j且重量不超过k的最大价值，在状态计算中相当于f[i-1][j][k]
选：这意味着我必须选第i个物品，然后在前i-1个物品中选择一些物品且体积不大于j-v且重量不超过k-m的最大价值在加上第i个物品的价值

状态转移方程：

不选：f[i][j][k] = f[i-1][j][k]
选： f[i][j][k] = f[i-1][j-v][k-m] + w

朴素版

开三维数组的话通常会超过数组的大小限制，所以我们需要优化

for (int i = 1; i <= n; i++)
{
    int v, m, w;
    cin >> v >> m >> w;
    for (int j = 0; j <= V; j++)
    {
        for (int k = 0; k <= M; k++)
        {
            f[i][j][k] = f[i - 1][j][k];
            if (j >= v && k >= m)
                f[i][j][k] = max(f[i][j][k], f[i - 1][j - v][k - m] + w);
        }
    }
}

优化版

我们像01背包那样优化就行了，过程差不多是一样的，只是多加了一维

for (int i = 1; i <= n; i++)
{
    int v, m, w;
    cin >> v >> m >> w;
    for (int j = V; j >= v; j--)
    {
        for (int k = M; k >= m; k--)
        {
            f[j][k] = max(f[j][k], f[j - v][k - m] + w);
        }
    }
}

6. 分组背包问题

有 NN 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 ii 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

基本思路：本题和01背包又有所不同，本题的要求是在每一组物品中选一个，最后求总价值最大是多少,其实核心还是01背包,对某一组内的物品都来一次01背包计算

状态表示： f[i][j]表示在前i组物品中选，体积不超过j的最大价值

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i组物品有多种选择，选哪一个

不选：意味着从前i-1组物品中选一些组中的一个物品且体积不大于j的最大价值，在状态计算中相当于f[i-1][j]
选第k个物品：这意味着我必须选第i组的第k物品，然后在前i-1个组中选择一些物品且体积不大于j-vik的最大价值在加上第k个物品的价值

状态转移方程：

不选：f[i][j] = f[i-1][j]
选： f[i][j] = f[i-1][j-vik] + wik

朴素版

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];          //第i组物品一个都不选
        for (int k = 1; k <= s[i]; k++) // 选第k个物品
        {
            if (j >= v[i][k])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
    }
}

优化成一维

for (int i = 1; i <= n; i++)
{
    for (int j = m; j >= 0; j--)
    {
        for (int k = 1; k <= s[i]; k++) // 选第k个物品
        {
            if (j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
        }
    }
}

7. 有依赖的背包问题

问题1 金明的预算方案

基本思路：可以将每个逐渐及其附件看作一个物品组，记主件为p,两个附件分别为a,b,则最多有四种组合， (p) （p a) (p b) (p a b)。而这四种组合是互斥的，最多只能从中选择一个物品，那么就变成了分组背包问题。

在枚举四种组合时可以使用二进制的思想，可以简化代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define v first
#define w second
const int N = 60, M = 4e4 + 10;
int n, m;      // n代表物品个数，m代表总钱数
PII master[N]; // 每个主件的价格和重要度
vector<PII> servent[N];
int f[M];
int main()
{
    cin >> m >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int v, w, p;
        cin >> v >> w >> p;
        if (p == 0)
            master[i] = {v, v * w}; //价值更改为为价值与重要度的乘积
        else
            servent[p].push_back({v, v * w});
    }
    for (int i = 1; i <= n; i++)
    {
        if (master[i].v)
        {
            for (int j = m; j >= 0; j--)
            {
                for (int k = 0; k < (1 << servent[i].size()); k++) //一组中的各个物品
                {
                    int v = master[i].v, w = master[i].w;
                    for (int u = 0; u < servent[i].size(); u++)
                    {
                        if (k >> u & 1)
                        {
                            v += servent[i][u].v;
                            w += servent[i][u].w;
                        }
                    }
                    if (j >= v)
                        f[j] = max(f[j], f[j - v] + w);
                }
            }
        }
    }
    cout << f[m];
    return 0;
}

8. 背包问题求方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

基本思路：本题就是在01背包的基础上加上了一个求方案数，只需要在开一个数组cnt[N][N]，定义为体积不超过j时的最优解的方案数

状态表示： f[i][j]表示在前i组物品中选，体积不超过j的最大价值，cnt[i][j]表示f[i][j]最大时的方案数

状态计算：

第i组物品有多种选择，选哪一个
1. 不选：意味着从前i-1组物品中选一些组中的一个物品且体积不大于j的最大价值，在状态计算中相当于f[i-1][j]
2. 选第k个物品：这意味着我必须选第i组的第k物品，然后在前i-1个组中选择一些物品且体积不大于j-vik的最大价值在加上第k个物品的价值
状态转移方程：
1. 不选：f[i][j] = f[i-1][j]
2. 选： f[i][j] = f[i-1][j-vik] + wik

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
typedef long long ll;
int f[N];
ll cnt[N];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i = 0; i <= m; i++) // 买0件物品，体积不超过j的方案数都是1
        cnt[i] = 1;
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--)
        {
            if (f[j - v] + w > f[j])
            {
                f[j] = f[j - v] + w;
                cnt[j] = cnt[j - v] % mod;
            }
            else if (f[j - v] + w == f[j])
            {
                cnt[j] = (cnt[j] + cnt[j - v]) % mod;
            }
        }
    }
    cout << cnt[m];
    return 0;
}

9. 背包问题求具体方案

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N1…N。

基本思路：题目要求输出字典序最小的解，假设存在一个包含第一个物品的解，为了确保字典序最小我们必须要选第一个，那么问题就转换成从2--n这些物品中找到最优解，之间的f[i][j]记录的都是前i个物品体积不超过j的最优解，现在我们考虑的是从n个物品到第i物品体积不超过j的最优解

状态表示： f[i][j]表示从n个物品到第i物品体积不超过j的最大价值

状态计算：

第i个物品有两种选择，选或不选
1. 不选：意味着从第i+1到第n个物品中选一些物品且体积不大于j的最大价值，在状态计算中相当于f[i+1][j]
2. 选：这意味着我必须选第i个物品，然后在第i+1到第n个物品中选择一些物品且体积不大于j-v的最大价值在加上第i个物品的价值
状态转移方程：
1. 不选：f[i][j] = f[i+1][j]
2. 选： f[i][j] = f[i+1][j-v] + w

现在我们要考虑如何得到最小字典序的解，首先f[1][m]一定是最大价值，那么我们开始考虑能否选择第1个物品呢？

如果f[1][m]==f[2][m-v[1]]+w[1],说明选取了第一个物品可以得到最大价值，那我们必须选择1号物品
如果f[1][m]==f[2][m],说明不选取第1个物品才能得到最大价值
如果f[i][m]==f[2][m]==f[2][m-v[i]]+w[1]，说明选不选第1个物品都可以得到最优解，但是为了字典序最小，我们也必须选择1号物品。

考虑其他物品也是这种思路

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int f[N][N];
int v[N], w[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for (int i = n; i >= 1; i--)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i + 1][j]; //因为物品数是从n到1枚举，所以每次都是由后一个的状态转换而来
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }
    int j = m;
    for (int i = 1; i <= n; i++) //字典序最小，所以从小到大枚举
    {
        // 能选必须选 ,因为要求字典序最小
        // 保证选第i个物品方案可行，也就是体积要满足
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            cout << i << " ";
            j -= v[i];
        }
    }
    return 0;
}

扩展1

题目详情 - L3-001 凑零钱 (pintia.cn)

如果把字典序中的编号最小改成物品的体积，也就说由物品体积构成的序列，那么该如何做呢，其实也不复杂，和本题类似，本体为了使编号的字典序最小，物品编号改成了从大到小枚举，最后选的一定是最小的，那么改成物品体积最小，我们只需将体积按着从大到小排序就可以了，物品从体积大的开始枚举

#include <bits/stdc++.h>
using namespace std;
#define v first
#define w second
const int N = 1e3 + 10;
typedef pair<int, int> PII;
int n, m;
int f[N][N];
PII goods[N]; // 记录每个物品的体积和价值
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        goods[i] = {v, w};
    }
    sort(goods + 1, goods + n + 1);
    for (int i = n; i >= 1; i--)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i + 1][j]; //因为物品数是从n到1枚举，所以每次都是由后一个的状态转换而来
            if (j >= goods[i].v)
                f[i][j] = max(f[i][j], f[i + 1][j - goods[i].v] + goods[i].w);
        }
    }
    int j = m;
    for (int i = 1; i <= n; i++) //字典序最小，所以从小到大枚举
    {
        // 能选必须选 ,因为要求字典序最小
        // 保证选第i个物品方案可行，也就是体积要满足
        if (j >= goods[i].v && f[i][j] == f[i + 1][j - goods[i].v] + goods[i].w)
        {
            cout << goods[i].v << " ";
            j -= goods[i].v;
        }
    }
    return 0;
}

扩展2

叠硬币

如果即要求体积的字典序最小且要求选的物品最少，又该怎么求呢？

基本思路：这里我们用f[N][N]数组来记录选择前i个物品体积不超过j时选择的物品最少的个数

状态表示： f[i][j]表示从n个物品到第i物品体积不超过j的最大价值

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有两种选择，选或不选

不选：意味着从前i-1个物品中选一些物品且体积不大于j的最优解，在状态计算中相当于f[i-1][j]
选：这意味着我必须选第i个物品，然后在前i-1个物品中选择一些物品且体积不大于j-v的最优解在加1(每个物品的价值相当于1)

状态转移方程：

不选：f[i][j] = f[i-1][j]
选： f[i][j] = f[i-1][j-v] + 1

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int f[N];
int v[N];
int pre[N]; // 这里我们用一个数组来记录最优方案，如果最优解被第i个物品更新，那么pre数组就更新为第i个物品的体积
int n, h;
signed main()
{
    //     freopen("in.in", "r", stdin);
    //     freopen("out.out", "w", stdout);
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    cin >> n >> h;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    // 将体积由大到小排序，最后选择的一定是字典序最小的
    sort(v + 1, v + n + 1, greater<int>());
    for (int i = 1; i <= n; i++)
    {
        for (int j = h; j >= v[i]; j--)
        {
            if (f[j] >= f[j - v[i]] + 1)
            {
                f[j] = f[j - v[i]] + 1;
                pre[j] = v[i];
            }
        }
    }
    if (f[h] == 0x3f3f3f3f)
    {
        cout << -1;
        return 0;
    }
    cout << f[h] << endl;
    while (h)
    {
        cout << pre[h] << " ";
        h -= pre[h];
    }
    return 0;
}

10 .体积不超过 j，恰好为 j，至少为 j 的区别

（一）体积不超过j

体积不超过j就是01背包，只要体积不超过j那就是合法方案

（二）体积恰好为j

只有被转移状态合法时才能被转移过来，我们以一道简单得题目为例

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数,问能否得到M

基本思路：注意本题和01背包的区别，本题不是求最大值，而是问这些数能不能组合为M，本题关注的是可行性，而不是最优解

状态表示： f[i][j]表示从前i个物品中选体积恰好为j时是否可行

状态计算：

如何计算f[i][j]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有两种选择，选或不选

不选：意味着从前i-1个物品中选一些物品且体积恰好为j的可行性，在状态计算中相当于f[i-1][j] ,如果f[i-1][j]可行，那么f[i][j]就可行
选：这意味着我必须选第i个物品，然后在前i-1个物品中选择一些物品且体积不大于j-v的可行性

状态转移方程：

不选：f[i][j]|=f[i-1[j]]

选：f[i][j]|=f[i-1][j-v]

优化代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
bool f[N];
signed main()
{
    f[0] = true;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        for (int j = m; j >= a; j--)
            f[j] |= f[j - a];
    }
    if(f[m])
        cout << "true";
    else
        cout << "false";
    return 0;
}

（三）体积至少是j

我们先来看一道题目潜水员

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120

10 25 129

5 50 250

1 45 130

4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

基本思路：每个物品只有一件，每件可以选择取或不取，运用闫氏dp法

状态表示： f[i,j,k]:所有从前i个物品中选,且氧气含量至少是j,氮气含量至少是k的所有选法的气缸重量总和的最小值,这里我们要理解这个至少的含义

状态计算：

如何计算f[i][j][k]?,考虑当前这一状态可以由什么状态转变而来，对于本题

第i个物品有两种选择，选或不选

不选：意味着从前i-1个物品中选一些物品且氧气至少是j且氮气至少是k的最优解，在状态计算中相当于f[i-1][j][k]
选：这意味着我必须选第i个物品，然后在前i-1个物品中选择一些物品氧气至少是j-v1且氮气至少是k-v2的最优解,这里我们需要注意j-v1或k-v2是可以为负数的，因为我们要求的是至少，至少是-1也是满足的，但是负数在数组是不能表示，我们就用0来表示负数，这里0和负数是等价的。

扩展
可能很多人会有这样的疑问，二维费用的背包问题的状态转移方程代码如下

for (int j = V; j >= v; j--)
    for (int k = M; k >= m; k--)
        f[j][k] = max(f[j][k], f[j - v][k - m] + w);

而本题的状态转移方程代码如下

for (int j = V; j >= 0; j--)
    for (int k = M; k >= 0; k--)
        f[j][k] = min(f[j][k], f[max(0, j - v)][max(0, k - m)] + w);

为什么上面的代码 j只需要遍历到v，k只能遍历到m。而下面的代码 j还需要遍历到0，k还需要遍历到0 ？同时为什么氧气或者氮气所需的是数量是负数时，可以与数量0的状态等价？

解答：对比两题的思路，二维费用的背包问题，求的是不能超过体积V，重量M的情况下，能拿到价值的最大值。而本题是至少需要体积V，重量M的情况下，能拿到价值的最小值。就拿体积来说，至少需要多少体积，也就是说有体积比需要的体积大的物品还是能用得到，例如f[3][5]，至少需要3个体积，5个重量，求能拿到价值的最小值，现在只有一个物品，体积是4，重量是4，价值w，它说至少需要3个体积，那么体积是4还是可以用到，只是多了1个体积没用占着而已，不影响其价值。因此若用了这个物品，则变成了求f[0][1] + w，表示体积已经不再需求了，只需要0个体积即可。

作者：小呆呆
链接： https://www.acwing.com/solution/content/7438/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int m, n, k;
int f[N][N];
signed main()
{
    cin >> m >> n >> k;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    while (k--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        for (int i = m; i >= 0; i--)
        {
            for (int j = n; j >= 0; j--)
            {
                f[i][j] = min(f[i][j], f[max(0, i - a)][max(0, j - b)] + c);
            }
        }
    }
    cout << f[m][n];
    return 0;
}

11.如果初始化 f 数组

求方案数初始化总结

二维情况

体积至多j，f[0][i] = 1, 0 <= i <= m，其余是0
体积恰好j，f[0][0] = 1, 其余是0
体积至少j，f[0][0] = 1，其余是0

一维情况

体积至多j，f[i] = 1, 0 <= i <= m，其余是0
体积恰好j，f[0] = 1, 其余是0
体积至少j，f[0] = 1，其余是0

求最大值最小值初始化总结
二维情况

体积至多j，f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）
体积恰好j
1. 当求价值的最小值：f[0][0] = 0, 其余是INF
2. 当求价值的最大值：f[0][0] = 0, 其余是-INF
体积至少j，f[0][0] = 0，其余是INF（只会求价值的最小值）

一维情况

体积至多j，f[i] = 0，0 <= i <= m（只会求价值的最大值，求最最小值一定是0，无意义啊）
体积恰好j
1. 当求价值的最小值：f[0] = 0, 其余是INF
2. 当求价值的最大值：f[0] = 0, 其余是-INF
体积至少j，f[0] = 0，其余是INF（只会求价值的最小值，求最大值那可以所有物品都选上，所以求最大值也无意义啊）

作者：小呆呆
链接： https://www.acwing.com/blog/content/458/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
感谢这位作者

你的背包背到现在还没烂

背书包的小新对背包问题的理解

1.01背包问题

2. 完全背包

3. 多重背包问题

4. 混合背包问题

5.二维费用的背包问题

6. 分组背包问题

7. 有依赖的背包问题

8. 背包问题求方案数

9. 背包问题求具体方案

10 .体积不超过 j，恰好为 j，至少为 j 的区别

11.如果初始化 f 数组

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

你的背包背到现在还没烂

背书包的小新对背包问题的理解

1.01背包问题

2. 完全背包

3. 多重背包问题

4. 混合背包问题

5.二维费用的背包问题

6. 分组背包问题

7. 有依赖的背包问题

8. 背包问题求方案数

9. 背包问题求具体方案

10 .体积不超过 j，恰好为 j，至少为 j 的区别

11.如果初始化 f 数组

热门文章

最新文章

相关电子书