多重背包

有一个容量为$V$的背包以及$n$种物品，第$i$种物品的体积为$c_i$价值为$w_i$个数为$1\lt s_i \lt M$，求将哪些物品装入背包可使背包里物品价值总和最大？

基本思路

$F[i, v] = \max \{ F[i-1, v-k*c_i] + k * w_i | 0\leq k \leq s_i \} $

朴素状态方程：

时间复杂度为$O(V\sum s_i )$

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

using namespace std;

const int N = 110;

int n, m;
int f[N];

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

优化改进

• 转化为0-1背包
• 转化为$s_i$件物品0-1背包问题

• 二进制分解：$2^0, 2^1, 2^2…2^{k-1}, s_i-2^k+1, k = \max \text{arg}_k \{ s_i - 2^k + 1 > 0 \} $ ,转换为$O(\log s_i)$件物品的0-1背包问题

• 单调队列优化

细品状态转移方程：

$ \quad F[i, j] = \max \{ F[i - 1, j - k * c_i] + k * w_i | 0 \leq k \leq s_i, 0 < j - k * c_i \} $

化简为一维形式：

$ \quad f[j] = \max \{ f[j - k * c_i] + k * w_i | 0 \leq k \leq s_i, 0 < j - k * c_i \} $

发现$f[j]$ 仅依赖于 $f[j - k * c_i]$， 按照依赖性可以对$f[j]$进行 $\mod c_i$ 分组：

f[0]        f[c]            f[2c]           ...     f[mc]
f[1]        f[1 + c]        f[1 + 2c]       ...     f[1 + mc]
f[2]        f[2 + c]        f[2 + 2c]       ...     f[2 + mc]
...
f[c - 1]    f[c - 1 + c]    f[c - 1 + 2c]   ...     f[c - 1 + mc]

假设当前物品只有3个，模拟下计算过程，有：

f[b]        f[b + c]        f[b + 2c]       f[b + 3c]       f[b + 4c]       f[b + 5c]
f[b]
f[b] + w    f[b + c]
f[b] + 2w   f[b + c] + w    f[b + 2c]
f[b] + 3w   f[b + c] + 2w   f[b + 2c] + w   f[b + 3c]
            f[b + c] + 3w   f[b + 2c] + 2w  f[b + 3c] + w   f[b + 4c] 
                            f[b + 2c] + 3w  f[b + 3c] + 2w  f[b + 4c] + w  f[b + 5c]

很熟悉的感觉，联想到了单调队列，看起来似乎是一种变种，如果构造转换如下：

f[b]   f[b + c]       f[b + 2c]        f[b + 3c]        f[b + 4c]        f[b + 5c]
f[b]
f[b]   f[b + c] - w   :: 全 - w
f[b]   f[b + c] - w   f[b + 2c] - 2w   :: 全 - 2w
f[b]   f[b + c] - w   f[b + 2c] - 2w   f[b + 3c] - 3w   :: 全 - 3w
       f[b + c] - w   f[b + 2c] - 2w   f[b + 3c] - 3w   f[b + 4c] - 4w   :: 全 - 4w
                      f[b + 2c] - 2w   f[b + 3c] - 3w   f[b + 4c] - 4w   f[b + 5c] -5W  : 全 - 5w

妥妥的单调队列场景！

数学推导如下：
$\quad f[j + p * c_i] = \max \{ f[j + k * c_i] + (p - k) * w_i | 0 \leq k \leq p \}$

$\quad f[j + p * c_i] - p * w_i = \max \{ f[j + k * c_i] - k * w_i | 0 \leq k \leq p \}$

则$f[j + p * c_i] - p * w_i $转换成了标准的滑动窗口单调队列形式，即$ f[x] - (x - j) / c_i * w_i$对于$x=j+p*c_i$构成单调队列。

yxc代码实现

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 20002;
int f[N], g[N], q[N]; // g: pre of f ; q: monotonic queue

int main(){
    cin >> n >> m;
    for (int i = 0; i <= n; i ++){
        int c, w, s;
        cin >> c >> w >> s;
        memcpy(g, f, sizeof(f));  // 

        for (int j = 0; j < c; j ++ ){      // mod c == j
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += c ){       // k = j + p * c
                // 滑窗大小为s
                if (hh <= tt && (k - q[hh]) / c > s)  ++hh;
                // 单调队列取最大值
                if (hh <= tt)  f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / c * w);
                // 维护单调队列
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / c * w <= g[k] - (k - j) / c * w){
                    -- tt;
                }
                q[++tt] = k;
            }
        }

    }
    cout << f[m] << endl;
}

Belous实现

#include <stdio.h>

const int  N  = 20002;

struct node{
    int pos, val;
}q[N];

int dp[N];

int main(){
    int n, m; scanf("%d%d", &n, &m);
    while (n--){
        int c, w, s; scanf("%d%d%d", &c, &w, &s);
        for (int j = 0; j < c; ++j){
            int hh = 0, tt = 0, max_k = (m - j) / c;
            for (int k = 0; k <= max_k; ++k){
                int cur_val = dp[j + k * c] - k * w;
                while (hh < tt && q[tt-1].val <= cur_val) --tt;
                q[tt++] = {k, cur_val};
                if (q[hh].pos < k - s) ++hh;
                dp[j + c * k] = q[hh].val + k * w;
            }
        }
    }
    printf("%d\n", dp[m]);
}

python3版13行

n, m = map(int, input().split())
dp, q = [0] * 20005, [None] * 20005     # q = [[pos, val], ...]
for _ in range(n):
    c, w, s = map(int, input().split())
    for j in range(c):
        hh = tt = 0
        for k in range((m - j)//c + 1):
            cur_val = dp[j + k * c] - k * w
            while hh < tt and q[tt - 1][1] <= cur_val: tt -= 1
            q[tt] = [k, cur_val]; tt += 1
            if q[hh][0] < k - s: hh += 1
            dp[j + c * k] = q[hh][1] + k * w
print(dp[m])