多重背包系列问题

问题简介

多重背包问题相对于完全背包问题最大的区别在于多重背包问题中每个物品的数量是有限的，但是二者的状态转移方程相同，故其可以由完全背包问题改写而来。

但是直接改写而来的朴素版本的完全背包问题本身无法应对较大的数据范围，故需要适当进行优化，本文便是针对该类常规的多重背包问题进行解答。

AcWing 5.多重背包问题II

当数据范围较小的时候可以考虑进行二进制优化，即将一组n个物品拆分为1个、2个、4个...，将问题转化为了01背包问题，即可以解决。

该问题的基本原理在于2的k次方可以表达出\(0\)到\(2^k - 1\)范围内的所有数字，故可以得到该种划分方式。

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;

int n, V, idx;
int cnt[N], w[N], v[N], f[N];

int main()
{
    cin >> n >> V;
    while(n --)
    {
        int tc, tw, tv;
        cin >> tv >> tw >> tc;
        
        int amt = 1;
        while(amt <= tc)
        {
            tc -= amt;
            w[idx] = tw * amt;
            v[idx] = tv * amt;
            amt <<= 1;
            idx ++;
        }
        
        if (tc != 0) 
        {
            w[idx] = tw * tc;
            v[idx] = tv * tc;
            idx ++;
        }
    }
    
    for (int i = 0; i < idx; ++i)
    {
        for (int j = V; j >= v[i]; --j)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[V];
}

AcWing 6.多重背包问题3

该问题中数据规模进一步扩大，原始的方法已经无法满足需求，故此时我们可以尝试去寻找规律去分析该问题。

首先我们可以将各个状态列出进行观察，有

f[i, j] 		= max(f[i - 1, j], f[i - 1, j - v] + w, f[i - 1, j - 2v] + 2w ... f[i - 1, j - sv] + sw)
f[i, j - v] = max(             f[i - 1, j - v],     f[i - 1, j - 2v] + w ...  f[i - 1, j - sv] + (s - 1)w + f[i - 1, j - (s + 1)v] + sw)
...

可以看到我们假设将物品全部选中后依旧不会超出容量的最大限制，此时f[i, j]与f[i, j - v]并不能如同完全背包问题那样对齐，故我们需要考虑其他的方法来解决这个问题。

当然，当我们列出剩下的每一项后我们可以发现一个规律，即该问题实际上是一个滑动窗口求最大值问题，即按照上面的对齐方式可以看出实际上f[i, j]除去第一项之后剩余项实际上可以看作是f[i, j - v]对应的窗口向固定方向滑动了一步。故根据这个特性我们便可以完成该题。可以考虑将上面的-更换为+，即从小到大递增。

但是此时我们还需要解决关于单调队列中偏移量的问题，在原始的式子中我们可以看到所有项后面都带着一个偏移量，而在单调队列转换的过程中就会出现单调队列最前方的项每次都需要+w的情况，如下所示

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

故可以考虑转换为

f[i, j] = max(f[i - 1, j] - sw, s[i - 1, j - v] - (s - 1)w, ..., f[i - 1, j - sv]) + sw

即此时我们的单调队列可以转换为针对转换后max()函数内的各项求单调队列，然后将总体的偏移量加回。

实际上最后我们的式子就被转换成了这样

f[i][j]      = max(f[i - 1][j])
f[i][j + v]  = max(f[i - 1][j], f[i - 1][j + v] - w) + w
f[i][j + 2v] = max(f[i - 1][j], f[i - 1][j + v] - w, f[i - 1][j + 2v] - 2w) + 2w;
...
f[i][j + nv] = max(f[i - 1][j + (n - s)v], f[i - 1][j + (n - s + 1)v] - w, ... f[i - 1][j + nv] - sv) + sv

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];
int v, w, s;

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; ++i)
    {
        cin >> v >> w >> s;
        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)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ; // 注意这里的k代表了总体积，即当k - s * v大于了队头保存的体积时将会弹出队头
                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; // 将偏移量加回
            }
        }
    }
    
    cout << f[m];
}