洛谷 P1776 宝物筛选

// P1776 第一版：把 m 件**摊开**成 m 件独立的物品，跑 01 背包
//
// [第 24 章第 ⑪ 步](/ch/24-knapsack-multi/)讲的就是它 —— 最直白，也一定对。
//
// ⚠ 复杂度 O(Σm × W)，顶格是 10^5 × 4×10^4 = **4 × 10^9** ⇒ 必 TLE。
//
// ★★ 但它**不是零分**：题面给了一档 30% 的数据（Σm ≤ 10^4，W ≤ 10^3）
//   ⇒ 那一档只有 10^7 次，随便过。解析页第 ③ 步把这 30 分量出来了。
//   ⇒ **「暴力能拿多少分」是一道三十秒的算术题**，而不是「反正过不了就不写」。

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

int main() {
    int n, W;
    if (!(cin >> n >> W)) return 0;
    vector<int> f(W + 1, 0);

    for (int i = 0; i < n; i++) {
        int v, w, m;
        cin >> v >> w >> m;
        for (int c = 0; c < m; c++)            // ⚠ 一件一件地摊开
            for (int j = W; j >= w; j--)
                f[j] = max(f[j], f[j - w] + v);
    }
    cout << f[W] << "\n";
    return 0;
}

// P1776 宝物筛选 —— ★ 这一版就能 AC（二进制拆分 + 01 背包）
//
// 题意：载重 W，n 种宝物，第 i 种价值 v[i]、重量 w[i]、**有 m[i] 件**。求最大价值。
//
// ⚠⚠ 先说一个和算法无关的坑：**输入是「v w m」，价值在前、重量在后** ——
//   而绝大多数背包题给的是「重量 价值」。读反了样例照样能过（见解析页第 ⑤ 步）。
//
// ★ 关键的一步：[第 24 章第 ⑫ 步](/ch/24-knapsack-multi/)的二进制拆分 ——
//   把「m 件相同的宝物」拆成 1, 2, 4, …, 2^(k-1), 余数 这几堆，
//   每堆当成**一件**新物品跑 01 背包。
//   凭什么对：这几个数能拼出 0 .. m 里的**每一个**整数（二进制表示），一个不多一个不少。
//
//   ⇒ 复杂度从 O(Σm × W) 变成 O(Σlog m × W)。
//     顶格 Σm = 10^5、W = 4×10^4 ⇒ 4 × 10^9 变成 6.5 × 10^7（解析页第 ③ 步量了）。
//
// ⚠ 拆分时**别忘了最后那一堆余数** —— 忘了它就凑不出某些件数（解析页第 ④ 步，
//   而那个 bug 有一个精确的触发条件：`m + 1 不是 2 的幂`）。

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

int main() {
    int n, W;
    if (!(cin >> n >> W)) return 0;
    vector<int> f(W + 1, 0);

    for (int i = 0; i < n; i++) {
        int v, w, m;
        cin >> v >> w >> m;                    // ⚠ 价值 v 在前，重量 w 在后
        for (int k = 1; m > 0; k <<= 1) {      // 1, 2, 4, 8, …
            int take = min(k, m);              // ★ 最后一堆是余数，不是 2 的幂
            m -= take;
            int cw = w * take, cv = v * take;
            for (int j = W; j >= cw; j--)      // 倒序：这一堆只用一次
                f[j] = max(f[j], f[j - cw] + cv);
        }
    }
    cout << f[W] << "\n";
    return 0;
}

// P1776 错法二：把「有 m 件」当成了「有无限件」（完全背包，内层正序）
//
// 拆分那一层写对了，可内层方向写成正序 —— 于是每一堆都能重复取，件数上限整个失效。
//
// ★ 说清楚它算了什么：它的答案**恒等于「每种宝物有无限多件」的完全背包答案**
//   （解析页第 ⑤ 步量成 300 组逐组相等）。
//   ⇒ 于是它的触发条件也是白送的：**只有当件数限制真的卡住了最优解时它才错。**

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

int main() {
    int n, W;
    if (!(cin >> n >> W)) return 0;
    vector<int> f(W + 1, 0);

    for (int i = 0; i < n; i++) {
        int v, w, m;
        cin >> v >> w >> m;
        for (int k = 1; m > 0; k <<= 1) {
            int take = min(k, m);
            m -= take;
            int cw = w * take, cv = v * take;
            for (int j = cw; j <= W; j++)      // ⚠ 正序 —— 这一堆能被反复取
                f[j] = max(f[j], f[j - cw] + cv);
        }
    }
    cout << f[W] << "\n";
    return 0;
}