混合背包

一、问题描述

有 $n$ 件物品和容量为 $V$ 的背包。第 $i$ 件物品的重量为 $w[i]$，价值为 $v[i]$，最多可以选择 $s[i]$ 件；若 $s[i]=0$，表示可以选择任意多件。

求总重量不超过 $V$ 时的最大总价值。每件物品的数量限制可以不同，因此问题中同时包含 01 背包、完全背包和多重背包，称为混合背包。

例题：YBT1377 混合背包。题目输入中的 P[i]=0 表示无限件，非零时表示最多可选 P[i] 件。

样例中，容量为 $10$，三件物品分别为 $(w,v,s)=(2,1,0),(3,3,1),(4,5,4)$。选择第一件 $1$ 件、第三件 $2$ 件，重量为 $10$，价值为 $11$。

二、按物品类型转移

设 dp[j] 表示当前处理过的物品中，总重量不超过 $j$ 时的最大总价值。初始时 dp[] 全为 $0$。

读入每件物品后，按数量限制选择对应的循环：

有限数量的物品可以拆成 $1,2,4,\ldots$ 件一组，末组取剩余件数。若一组含 $c$ 件原物品，就把它当作一件重量为 $c\cdot w[i]$、价值为 $c\cdot v[i]$ 的 01 背包物品。拆分后的各组能够组合出从 $0$ 到数量上限的所有件数。

因为容量只有 $V$，每种物品最多只需考虑 $\lfloor V/w[i]\rfloor$ 件。因此有限物品先令 s = min(s, V / w)，再进行二进制拆分。

三、参考代码

输入第一行为背包容量 $V$ 和物品数 $n$。接下来 $n$ 行，每行输入重量、价值和数量限制 w v s；s=0 表示无限件。题目数据中物品重量为正。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_V = 205;
long long dp[MAX_V];
int V, n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> V >> n;

    for (int i = 1; i <= n; ++i) {
        int w, s;
        long long v;
        cin >> w >> v >> s;

        if (s == 0) {
            // 完全背包：允许重复选择，容量正序
            for (int j = w; j <= V; ++j) dp[j] = max(dp[j], dp[j - w] + v);
        } else {
            // 有限数量：超过容量所能容纳的数量没有意义
            s = min(s, V / w);
            // 二进制拆分，每组作为一个 01 背包物品
            for (int c = 1; s > 0; c *= 2) {
                int take = min(c, s);
                int weight = take * w;
                long long value = 1LL * take * v;
                for (int j = V; j >= weight; --j) dp[j] = max(dp[j], dp[j - weight] + value);
                s -= take;
            }
        }
    }
    cout << dp[V] << '\n';
    return 0;
}

四、复杂度

无限件物品进行一次 $O(V)$ 的完全背包转移。有限件数先按背包容量截断，再拆成 $O(\log(V+1))$ 组，每组进行一次 $O(V)$ 的 01 背包转移。

总时间复杂度为 $O(nV\log(V+1))$，DP 空间复杂度为 $O(V)$。