洛谷 P1757 通天之分组背包

// ✗ P1757 的第一个坑，和算法一点关系都没有：第一行两个数读反了。
//
// 题面第一句是「两个数 `m, n`，表示一共有 `n` 件物品，背包能承受的最大重量为 `m`」——
// **先容量、后件数**，而绝大多数背包题是反过来的。
//
// ★ 这一版把它读成了 `n m`。官方样例 `45 3` 于是变成「45 件物品、容量 3」：
//   后面只有 3 行可读，读完就没了 ⇒ 打出 0。**样例当场挡住。**
// ⚠ 这份代码老老实实检查了 `scanf` 的返回值 —— 读不到就停，
//   免得拿一堆未初始化的垃圾去做 DP（那样打出来的数**换个编译器就变**，没法写进正文）。

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

int main() {
    int m, n;
    if (scanf("%d %d", &n, &m) != 2) return 0;       // ✗ 读反了
    map<int, vector<pair<int, int>>> by;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        if (scanf("%d %d %d", &a, &b, &c) != 3) break;   // 读不到就停
        by[c].push_back({ a, b });
    }
    if (m < 0) m = 0;
    vector<int> f(m + 1, 0);
    for (auto& kv : by)
        for (int j = m; j >= 0; j--)
            for (auto& it : kv.second)
                if (it.first <= j) f[j] = max(f[j], f[j - it.first] + it.second);
    printf("%d\n", f[m]);
    return 0;
}

// P1757 通天之分组背包 —— ★ 这一版就能 AC。
//
// 第 25 章下半场那三层循环，原样搬过来：
//     for 每一组
//         for j = m .. 0        ← 容量，倒序
//             for 组内每一件
//                 f[j] = max(f[j], f[j - a] + b)
//
// ⚠ 这道题真正要过的第一关不是 DP，是**读入**：
//   ① 第一行是 `m n` —— **先容量、后件数**（读反了会读到一堆垃圾，见 p1757Swap.cpp）；
//   ② 物品是「每件自带组号」，要先按组号归类；
//   ③ ★★ 而**组号不是 1..k** —— 题面写的是「`1 ≤ k ≤ 100`」（**组数**至多 100），
//      管理员备注又写着「`0 ≤ cᵢ ≤ 10⁴`」（**组号**能到一万）。这两句差 100 倍。
//      ⇒ 这里用一张 `10001` 个桶的表归类，再把**真正出现过**的组号收集起来跑。

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

const int MAXC = 10000;

int main() {
    int m, n;
    if (scanf("%d %d", &m, &n) != 2) return 0;       // ★ 先 m（容量）后 n（件数）
    vector<vector<pair<int, int>>> grp(MAXC + 1);    // grp[组号] = {(重量, 价值), ...}
    vector<int> ids;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        if (scanf("%d %d %d", &a, &b, &c) != 3) return 0;
        if (c < 0 || c > MAXC) continue;
        if (grp[c].empty()) ids.push_back(c);
        grp[c].push_back({ a, b });
    }

    vector<int> f(m + 1, 0);
    for (int c : ids)
        for (int j = m; j >= 0; j--)                 // 容量倒序：读到的 f[j-a] 还没被本组碰过
            for (auto& it : grp[c])                  // 组内枚举必须在最里层
                if (it.first <= j) f[j] = max(f[j], f[j - it.first] + it.second);
    printf("%d\n", f[m]);
    return 0;
}

// ✗ P1757 的第二个坑：照着「`1 ≤ k ≤ 100`」这一行，把组号也当成了 1..100。
//
// 题面数据范围里那一行写着 `1 ≤ k ≤ 100`，而 `k` 在题目描述里指的是「物品大致可分为 k 组」——
// 也就是**组数**。可管理员备注里另写了一句：`0 ≤ cᵢ ≤ 10⁴` —— 那是**组号的取值范围**。
//
// ★★ 这两句差 **100 倍**，而它们说的是两件事：
//     「有几组」是 100，「组号能有多大」是 10 000。
//
// 这一版只扫组号 1..100，于是组号更大的那些物品**整组被漏掉**（答案偏小）。

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

int main() {
    int m, n;
    if (scanf("%d %d", &m, &n) != 2) return 0;
    vector<vector<pair<int, int>>> grp(101);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        if (scanf("%d %d %d", &a, &b, &c) != 3) return 0;
        if (c >= 1 && c <= 100) grp[c].push_back({ a, b });   // ✗ 组号 > 100 的全丢了
    }
    vector<int> f(m + 1, 0);
    for (int c = 1; c <= 100; c++)
        for (int j = m; j >= 0; j--)
            for (auto& it : grp[c])
                if (it.first <= j) f[j] = max(f[j], f[j - it.first] + it.second);
    printf("%d\n", f[m]);
    return 0;
}

// ✗ P1757 的第三个坑：组内那层循环提到了容量循环**外面**。
//
// 第 25 章正文第 11 步那张表：三层循环的顺序**决定你解的是哪一道题**。
// 组 → 组内 → 容量倒序，读到的 `f[j-a]` 是「本组已经放过一件」的值 ⇒ 同一组能拿好几件。
//
// ★ 它不是「随便错」：它精确地等于**无视分组的 01 背包**（p1757Ignore.cpp），300 轮逐组相等。

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

int main() {
    int m, n;
    if (scanf("%d %d", &m, &n) != 2) return 0;
    map<int, vector<pair<int, int>>> by;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        if (scanf("%d %d %d", &a, &b, &c) != 3) return 0;
        by[c].push_back({ a, b });
    }
    vector<int> f(m + 1, 0);
    for (auto& kv : by)
        for (auto& it : kv.second)                  // ✗ 组内提到了外面
            for (int j = m; j >= it.first; j--)
                f[j] = max(f[j], f[j - it.first] + it.second);
    printf("%d\n", f[m]);
    return 0;
}