完全背包与多重背包

// 完全背包 —— 暴力：DFS 枚举「第 i 件拿几个」
//
// 为什么不能像第 23 章那样用 2ⁿ 枚举子集：完全背包里每件物品有**无限多件**，
// 「拿或不拿」不够用了，得问「拿几个」—— 而「几个」的上界是 W / w[i]，
// 于是搜索树的分叉数不再是 2，而是每层各不相同。
//
// 这份代码是这一章第一个对拍的标准答案。它慢得离谱，但它绝对不会错，
// 因为它根本没有「想法」，只是把所有拿法都试了一遍。
//
// 题意：n 种物品，第 i 种价值 v[i]、重量 w[i]，**每种可以拿任意多件**（包括 0 件）。
//       背包最多装 W。求最大总价值。
// 输入：第一行 n W，接下来 n 行每行两个数 v w
// 输出：最大总价值
//
// ⚠ 只能用在很小的数据上（fullGen.cpp 造的是 n ≤ 6、W ≤ 24）。
//   W = 100、w[i] = 1 时这棵树就有 100 层分叉，跑到天荒地老。

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

int n;
long long W, best;
vector<long long> v, w;

// 处理到第 i 种物品，还剩 rest 的容量，已经攒了 got 的价值
void dfs(int i, long long rest, long long got) {
    if (i == n) { best = max(best, got); return; }
    // 第 i 种拿 k 件，k 从 0 一直到装不下为止
    for (long long k = 0; k * w[i] <= rest; k++)
        dfs(i + 1, rest - k * w[i], got + k * v[i]);
}

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

    if (!(cin >> n >> W)) return 0;
    v.resize(n);
    w.resize(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    best = 0;
    dfs(0, W, 0);
    cout << best << "\n";
    return 0;
}

// 完全背包 —— 朴素二维：把「拿几个」直接写进转移
//
// 从暴力到正解之间的那一级台阶。照着第 23 章的思路改，最自然的写法就是它：
//
//   f[i][j] = max{ f[i-1][j - k*w[i]] + k*v[i] }   k = 0, 1, 2, ... 只要装得下
//
// 也就是「第 i 种拿 0 件、1 件、2 件……分别是多少，取最大的」。
// 它是对的，但**多了一层 k 的循环**：复杂度 O(n × W × W/w)，最坏 O(nW²)。
//
// W = 5000 时 W² 就是两千五百万，再乘 n 就跑不动了 —— 这一章的 ★ 就是来砍掉这层 k 的。
//
// 输入输出同 fullBrute.cpp。这份代码在正文里的作用是**当对照组**：
// 它和 full.cpp 答案永远相同，只是慢得多。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    vector<vector<long long>> f(n + 1, vector<long long>(W + 1, 0));

    for (int i = 1; i <= n; i++)
        for (long long j = 0; j <= W; j++)
            for (long long k = 0; k * w[i] <= j; k++)                 // ← 多出来的这一层
                f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]);

    cout << f[n][W] << "\n";
    return 0;
}

// 完全背包 —— 正解。和第 23 章的 fast.cpp 只差一个方向
//
//   01 背包  ：for (long long j = W; j >= w[i]; j--)     ← 倒序
//   完全背包：for (long long j = w[i]; j <= W; j++)     ← 正序
//
// ★ 这一章的关键一步，其实是**把 fullNaive.cpp 那层 k 的循环砍掉**。
//   先看二维：把「第 i 种拿了至少一件」这件事单独拎出来 ——
//
//     不拿第 i 种         ： f[i][j] = f[i-1][j]
//     至少拿一件第 i 种   ： f[i][j] = f[i][j - w[i]] + v[i]
//                                      ↑↑↑ 注意第一维是 **i**，不是 i-1
//
//   为什么可以是 i：f[i][j-w[i]] 的含义是「前 i 种物品、容量 j-w[i] 的最优解」，
//   而第 i 种**本来就允许再拿**，所以在它上面直接加一件是合法的 ——
//   而且它内部已经把「第 i 种拿 2 件、3 件……」的情况全都算进去了。
//   于是「拿 k 件」这层循环就被一句「拿一件」递归地包含了。
//
//   ⚠ 和第 23 章正好相反，那里的铁律是「右边的第一维必须是 i-1」（每件最多一件）；
//     这里的铁律是「右边的第一维就是 i」（每件想拿几件拿几件）。
//     **是题目决定了写 i 还是 i-1，倒序 / 正序只是它在一维下的写法。**
//
// 压成一维之后：读 f[j - w[i]] 时希望读到的是**本轮已经更新过**的值，
// 所以 j 要从小到大 —— 正序。
//
// 输入输出同 fullBrute.cpp。复杂度 O(nW) 时间、O(W) 空间。
//
// 这份代码和第 23 章的 complete.cpp 一模一样（那里是当反例出现的）。
// 你在上一章亲手确认过：01 背包写成正序，跑出来的就是完全背包的正确答案。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    vector<long long> f(W + 1, 0);

    for (int i = 1; i <= n; i++)
        for (long long j = w[i]; j <= W; j++)          // ★ 正序！倒着写就变回 01 背包
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[W] << "\n";
    return 0;
}

// 完全背包写成倒序 —— 这是一份**故意写错**的代码，而且它错得和上一章完全对称
//
// 第 23 章：01 背包写成正序  → 跑出来的是**完全背包**的正确答案
// 这一章  ：完全背包写成倒序 → 跑出来的是**01 背包**的正确答案
//
// 两个「bug」互为对方的正确解法。这不是巧合，是同一句话的两面：
// **方向决定了 f[j-w] 是「这一轮的」还是「上一轮的」，
//   也就决定了同一种物品能不能被反复拿。**
//
// check-viz 把这件事钉死了：用 fullGen.cpp 造 300 组数据，
// 这份代码的输出和第 23 章 `code/23-knapsack-01/fast.cpp` 的输出**300 组一模一样**。
//
// 所以「完全背包正序、01 背包倒序」这两句口诀，你只要记住其中任何一句 ——
// 另一句是它的反面，忘了就现推。
//
// 输入输出同 fullBrute.cpp。把它贴进对拍器（标准答案用 fullBrute.cpp）看看第几轮被抓。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    vector<long long> f(W + 1, 0);

    for (int i = 1; i <= n; i++)
        for (long long j = W; j >= w[i]; j--)          // ✗ 倒序：每种就只能拿一件了
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[W] << "\n";
    return 0;
}

// 多重背包 —— 暴力：DFS 枚举「第 i 种拿几件」（0 ~ k[i]）
//
// 这一章第二个对拍的标准答案。和 fullBrute.cpp 只差一处：
// 每种物品的件数不再是「无限」，而是最多 k[i] 件。
//
// ★ 它是**完全不同的思路**：不做任何 DP，也不做任何拆分，只是把所有拿法试一遍。
//   这一点很重要 —— multiNaive.cpp 和 multi.cpp 本质上都是「拆成 01 背包再 DP」，
//   拿它们互相对拍只能验出打字错误，验不出「拆分本身就想错了」。
//   （第 20 章那条规矩：**标准答案最好用完全不同的思路写。**）
//
// 题意：n 种物品，第 i 种价值 v[i]、重量 w[i]、**最多 k[i] 件**。背包最多装 W。
// 输入：第一行 n W，接下来 n 行每行三个数 v w k
// 输出：最大总价值
//
// ⚠ 只能用在很小的数据上（multiGen.cpp 造的是 n ≤ 5、W ≤ 30）。

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

int n;
long long W, best;
vector<long long> v, w, cnt;

void dfs(int i, long long rest, long long got) {
    if (i == n) { best = max(best, got); return; }
    for (long long t = 0; t <= cnt[i] && t * w[i] <= rest; t++)
        dfs(i + 1, rest - t * w[i], got + t * v[i]);
}

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

    if (!(cin >> n >> W)) return 0;
    v.resize(n);
    w.resize(n);
    cnt.resize(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> cnt[i];

    best = 0;
    dfs(0, W, 0);
    cout << best << "\n";
    return 0;
}

// 多重背包 —— 朴素做法：把「k 件同样的物品」拆成 k 件独立的物品，跑 01 背包
//
// 这是最该先想到的做法，而且它一点都不丢人：**转化**本身就是正确的思路，
// 「第 i 种最多拿 k 件」和「有 k 件一模一样的物品，每件最多拿一件」是同一件事。
//
// 而且它顺手回答了一个常见疑问：多重背包**不能**用完全背包的正序写法，
// 因为正序会让同一种物品被拿无限多次，管不住「最多 k 件」这个上限。
// 拆成 01 之后，倒序照旧。
//
// 复杂度 O(W × Σk[i])。k 全是 1 时它就是 01 背包，k 很大时它会炸：
// 100 种物品、每种 1000 件、W = 5000 → 5000 × 100000 = 5 亿格。
// ★ 这一章第二个关键一步（二进制拆分）就是来砍这个 Σk 的。
//
// 这份代码在正文里的作用是**中间台阶 + 对照组**：
// 它和 multi.cpp 答案永远相同，只是慢得多。
//
// 输入输出同 multiBrute.cpp。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;

    // 拆：第 i 种的 k 件，一件一件地摊开
    vector<pair<long long, long long>> items;        // (价值, 重量)
    long long total = 0;
    for (int i = 0; i < n; i++) {
        long long v, w, k;
        cin >> v >> w >> k;
        total += k;
        for (long long t = 0; t < k; t++) items.push_back({v, w});
    }

    vector<long long> f(W + 1, 0);
    for (auto [v, w] : items)
        for (long long j = W; j >= w; j--)           // 拆成 01 之后，倒序照旧
            f[j] = max(f[j], f[j - w] + v);

    cout << f[W] << "\n";
    // 顺带把摊开之后的物品件数打到 stderr，方便和 multi.cpp 对比（不影响对拍）
    cerr << "摊开成 " << total << " 件 01 物品\n";
    return 0;
}

// 多重背包 —— 正解：二进制拆分 + 01 背包
//
// ★ 这一章第二个关键一步。
//
// multiNaive.cpp 把 k 件摊成 k 件独立物品，于是有 Σk 件要处理。
// 但仔细想想：我们真正需要的只是「**能凑出 0 ~ k 之间的任意件数**」，
// 至于是怎么凑出来的，DP 并不关心。
//
// 而「用最少的堆凑出 0 ~ k 的所有整数」这件事，第 3 章已经给过答案了 ——
// **二进制**。把 k 拆成
//
//     1, 2, 4, 8, ..., 2^(t-1),  k - (2^t - 1)
//
// 其中 t 是使 2^t - 1 ≤ k 的最大值，最后那一堆是余数（可能为 0，就不要了）。
//
// 为什么这样拆一定够用：
//   前面那些 1,2,4,...,2^(t-1) 可以凑出 0 ~ 2^t-1 的每一个整数（这就是二进制表示）；
//   再加上余数那一堆，就能凑出 (k-2^t+1) ~ k。两段接得上（因为余数 ≤ 2^t-1），
//   所以 0 ~ k 一个不漏。而且**凑不出比 k 大的数**（总和正好是 k），上限也管住了。
//
// 举例：k = 13 → 1, 2, 4, 6（4 堆）。想拿 11 件？6 + 4 + 1。想拿 3 件？2 + 1。
//       split.cpp 会把 0 ~ k 每个数都验一遍。
//
// 于是件数从 k 降到 ⌈log₂(k+1)⌉：k = 1000 时从 1000 堆降到 10 堆，**一百倍**。
// 复杂度 O(W × Σlog k[i])。
//
// 拆完之后每一堆当成一件普通的 01 物品（价值 t·v、重量 t·w），倒序照旧 ——
// 因为每一堆**只能整堆拿或整堆不拿**，正是 01 背包。
//
// 输入输出同 multiBrute.cpp。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;

    vector<pair<long long, long long>> items;        // (价值, 重量)，每个元素是一「堆」
    long long piles = 0;
    for (int i = 0; i < n; i++) {
        long long v, w, k;
        cin >> v >> w >> k;
        for (long long t = 1; t <= k; k -= t, t <<= 1) {   // t = 1, 2, 4, 8, ...
            items.push_back({t * v, t * w});
            piles++;
        }
        if (k > 0) { items.push_back({k * v, k * w}); piles++; }   // 剩下的余数单独成一堆
    }

    vector<long long> f(W + 1, 0);
    for (auto [v, w] : items)
        for (long long j = W; j >= w; j--)           // 每堆只能整堆拿，所以是 01 背包 → 倒序
            f[j] = max(f[j], f[j - w] + v);

    cout << f[W] << "\n";
    cerr << "拆成 " << piles << " 堆\n";
    return 0;
}

// 把二进制拆分**拆给你看**，并且逐个验证「0 ~ k 每个件数都凑得出来」
//
// 为什么要有这份代码：二进制拆分的正确性是一句话带过的
//（「1,2,4,… 能凑出二进制表示的每一个数」），但一句话说服不了人。
// 这份代码对每个 k 都把 0 ~ k 全枚举一遍，真的去检查每个数能不能由那些堆凑出来。
//
// ★ 顺带把这一步真正的收益量出来：k 从 1000 降到 10 堆，是一百倍，不是一点点。
//
// 拆法：t = 1, 2, 4, 8, ... 每次从 k 里扣掉 t，扣不动了就把剩下的余数单独成一堆。
//
// 输入：一行若干个 k（空格隔开）。不给输入就用一组默认的 k。
// 输出：一张表。每行是「k / 朴素要几件 / 拆成几堆 / 具体怎么拆 / 零到 k 是不是全能凑出」
//
// ⚠ 表头里一个数字都不能有 —— check-viz 是按「行里的数字」解析这张表的，
//   表头混进数字会被当成数据（第 20 章的 knapTable.cpp 就踩过这个坑）。

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

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

    vector<long long> ks;
    long long x;
    while (cin >> x) if (x >= 0) ks.push_back(x);
    if (ks.empty()) ks = {1, 2, 3, 4, 5, 7, 8, 13, 100, 1000};

    cout << "     k   朴素件数   二进制堆数   拆法                             零到 k 全能凑出\n";
    cout << "  ----   --------   ----------   ------------------------------   ---------------\n";

    for (long long k : ks) {
        vector<long long> piles;
        long long rest = k;
        for (long long t = 1; t <= rest; rest -= t, t <<= 1) piles.push_back(t);
        if (rest > 0) piles.push_back(rest);

        // 这些堆能凑出哪些件数？（子集和，布尔 DP）
        vector<char> ok(k + 1, 0);
        ok[0] = 1;
        for (long long p : piles)
            for (long long j = k; j >= p; j--)       // 每堆只能用一次 → 01 背包 → 倒序
                if (ok[j - p]) ok[j] = 1;
        bool all = true;
        for (long long j = 0; j <= k; j++) if (!ok[j]) all = false;

        string how;
        for (size_t i = 0; i < piles.size(); i++) {
            if (i) how += "+";
            how += to_string(piles[i]);
        }

        cout << setw(6) << k << setw(11) << k << setw(13) << (long long)piles.size()
             << "   " << left << setw(33) << how << right
             << (all ? "是" : "否") << "\n";
    }
    return 0;
}

// 完全背包 —— 正解。和第 23 章的 fast.cpp 只差一个方向
//
//   01 背包  ：for (long long j = W; j >= w[i]; j--)     ← 倒序
//   完全背包：for (long long j = w[i]; j <= W; j++)     ← 正序
//
// ★ 这一章的关键一步，其实是**把 fullNaive.cpp 那层 k 的循环砍掉**。
//   先看二维：把「第 i 种拿了至少一件」这件事单独拎出来 ——
//
//     不拿第 i 种         ： f[i][j] = f[i-1][j]
//     至少拿一件第 i 种   ： f[i][j] = f[i][j - w[i]] + v[i]
//                                      ↑↑↑ 注意第一维是 **i**，不是 i-1
//
//   为什么可以是 i：f[i][j-w[i]] 的含义是「前 i 种物品、容量 j-w[i] 的最优解」，
//   而第 i 种**本来就允许再拿**，所以在它上面直接加一件是合法的 ——
//   而且它内部已经把「第 i 种拿 2 件、3 件……」的情况全都算进去了。
//   于是「拿 k 件」这层循环就被一句「拿一件」递归地包含了。
//
//   ⚠ 和第 23 章正好相反，那里的铁律是「右边的第一维必须是 i-1」（每件最多一件）；
//     这里的铁律是「右边的第一维就是 i」（每件想拿几件拿几件）。
//     **是题目决定了写 i 还是 i-1，倒序 / 正序只是它在一维下的写法。**
//
// 压成一维之后：读 f[j - w[i]] 时希望读到的是**本轮已经更新过**的值，
// 所以 j 要从小到大 —— 正序。
//
// 输入输出同 fullBrute.cpp。复杂度 O(nW) 时间、O(W) 空间。
//
// 这份代码和第 23 章的 complete.cpp 一模一样（那里是当反例出现的）。
// 你在上一章亲手确认过：01 背包写成正序，跑出来的就是完全背包的正确答案。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    vector<long long> f(W + 1, 0);

    for (int i = 1; i <= n; i++)
        for (long long j = w[i]; j <= W; j++)          // ★ 正序！倒着写就变回 01 背包
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[W] << "\n";
    return 0;
}

// 多重背包 —— 正解：二进制拆分 + 01 背包
//
// ★ 这一章第二个关键一步。
//
// multiNaive.cpp 把 k 件摊成 k 件独立物品，于是有 Σk 件要处理。
// 但仔细想想：我们真正需要的只是「**能凑出 0 ~ k 之间的任意件数**」，
// 至于是怎么凑出来的，DP 并不关心。
//
// 而「用最少的堆凑出 0 ~ k 的所有整数」这件事，第 3 章已经给过答案了 ——
// **二进制**。把 k 拆成
//
//     1, 2, 4, 8, ..., 2^(t-1),  k - (2^t - 1)
//
// 其中 t 是使 2^t - 1 ≤ k 的最大值，最后那一堆是余数（可能为 0，就不要了）。
//
// 为什么这样拆一定够用：
//   前面那些 1,2,4,...,2^(t-1) 可以凑出 0 ~ 2^t-1 的每一个整数（这就是二进制表示）；
//   再加上余数那一堆，就能凑出 (k-2^t+1) ~ k。两段接得上（因为余数 ≤ 2^t-1），
//   所以 0 ~ k 一个不漏。而且**凑不出比 k 大的数**（总和正好是 k），上限也管住了。
//
// 举例：k = 13 → 1, 2, 4, 6（4 堆）。想拿 11 件？6 + 4 + 1。想拿 3 件？2 + 1。
//       split.cpp 会把 0 ~ k 每个数都验一遍。
//
// 于是件数从 k 降到 ⌈log₂(k+1)⌉：k = 1000 时从 1000 堆降到 10 堆，**一百倍**。
// 复杂度 O(W × Σlog k[i])。
//
// 拆完之后每一堆当成一件普通的 01 物品（价值 t·v、重量 t·w），倒序照旧 ——
// 因为每一堆**只能整堆拿或整堆不拿**，正是 01 背包。
//
// 输入输出同 multiBrute.cpp。

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;

    vector<pair<long long, long long>> items;        // (价值, 重量)，每个元素是一「堆」
    long long piles = 0;
    for (int i = 0; i < n; i++) {
        long long v, w, k;
        cin >> v >> w >> k;
        for (long long t = 1; t <= k; k -= t, t <<= 1) {   // t = 1, 2, 4, 8, ...
            items.push_back({t * v, t * w});
            piles++;
        }
        if (k > 0) { items.push_back({k * v, k * w}); piles++; }   // 剩下的余数单独成一堆
    }

    vector<long long> f(W + 1, 0);
    for (auto [v, w] : items)
        for (long long j = W; j >= w; j--)           // 每堆只能整堆拿，所以是 01 背包 → 倒序
            f[j] = max(f[j], f[j - w] + v);

    cout << f[W] << "\n";
    cerr << "拆成 " << piles << " 堆\n";
    return 0;
}