洛谷 P1048 [NOIP 2005 普及组] 采药

// P1048 [NOIP 2005 普及组] 采药 —— ★ 这一版就能 AC（01 背包）
//
// 题意：M 株草药，第 i 株要花 t_i 时间、值 v_i；总时间 T，每株**要么整株采、要么不采**，求最大总价值。
//
// ★ 这就是**01 背包**的模板题，而它挂在[第 20 章](/ch/20-greedy-proof/)的题单里是为了别的事：
//   题单里写着「**故意先用性价比贪心交一发，看着它 WA**，再学第 23 章的 DP。这一发 WA 值得挨」。
//   ⇒ 这一页就把那一发**值多少分**量出来（页面第 ③ ④ 步）。
//
// DP：`f[j]` = 时间恰好用不超过 j 时的最大价值。
//   `f[j] = max(f[j], f[j - t_i] + v_i)`，**j 必须从大到小枚举**。
//   ⚠ 从小到大就变成了**完全背包**（同一株草药能采好几次）——
//     页面第 ⑤ 步把这件事量成了「它逐组等于完全背包的答案」，而**官方样例正好挡住了它**。
//
// 复杂度 `O(T M)`，顶格 1000 × 100 = 10⁵ —— 小得可以忽略。

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

int main() {
    int T, m;
    if (!(cin >> T >> m)) return 0;
    vector<int> t(m), v(m);
    for (int i = 0; i < m; i++) cin >> t[i] >> v[i];

    vector<int> f(T + 1, 0);
    for (int i = 0; i < m; i++)
        for (int j = T; j >= t[i]; j--)              // ★ 倒序：每株草药只能用一次
            f[j] = max(f[j], f[j - t[i]] + v[i]);

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

// P1048 的参照物：**枚举所有子集**（采 / 不采），`2^M`
//
// ★ 它不需要任何想法 —— 而这一页要验的恰恰是「哪个想法是对的」，
//   所以参照物必须离开「排序 + 贪心」和「DP」两条路。
// ⚠ 只跑得动 `M ≤ 22` 左右；题面 30% 的数据是 `M ≤ 10`，那一档正好够。

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

int main() {
    int T, m;
    if (!(cin >> T >> m)) return 0;
    vector<int> t(m), v(m);
    for (int i = 0; i < m; i++) cin >> t[i] >> v[i];

    int best = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int st = 0, sv = 0;
        for (int i = 0; i < m; i++)
            if (mask >> i & 1) { st += t[i]; sv += v[i]; }
        if (st <= T) best = max(best, sv);
    }
    cout << best << "\n";
    return 0;
}

// P1048 错法一：★★★ 按**性价比**（v / t）从高到低贪心 —— 第 20 章那个「最著名的上当」
//
// 直觉非常强：「每分钟能采到的价值最高的先采」。
// 它在**部分背包**（能把草药切开）里是**对的**（见同一天那份 [P2240](/sol/p2240/)），
// 而在这里 —— 草药只能整株采 —— **是错的**。
//
// ★ 交换论证在这里断在哪：部分背包能把 δ 从低性价比换成高性价比，重量不变；
//   01 背包换不了 —— 你只能整株拿或整株不拿，「换 δ」这个动作不存在。
//
// ⚠ 而它错得**不多**（页面第 ③ 步量了）：多数随机数据上它只差几个百分点，
//   所以「样例过了、随手试几组也对」是这个上当的常态。
// ★ 比较用交叉相乘（`v1 * t2 > v2 * t1`），全整数，没有浮点。

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

int main() {
    int T, m;
    if (!(cin >> T >> m)) return 0;
    vector<pair<int, int>> a(m);                     // (时间, 价值)
    for (auto& p : a) cin >> p.first >> p.second;

    sort(a.begin(), a.end(), [](const pair<int, int>& x, const pair<int, int>& y) {
        return (long long)x.second * y.first > (long long)y.second * x.first;   // v1/t1 > v2/t2
    });

    int cap = T, ans = 0;
    for (auto& [t, v] : a)
        if (t <= cap) { cap -= t; ans += v; }        // 整株采，采不下就跳过
    cout << ans << "\n";
    return 0;
}

// P1048 错法三：DP 的第二层循环写成**从小到大**
//
// 一维 01 背包只有一行需要小心：`for (int j = T; j >= t[i]; j--)`。
// 写成 `for (int j = t[i]; j <= T; j++)` 之后，`f[j - t[i]]` 已经是**这一轮更新过的**了 ——
// 于是同一株草药可以被采好几次。
//
// ★★ 说清楚它**算了什么**比说它「错了」有用：**它精确地在解完全背包**
//   （页面第 ⑤ 步把这件事量成了「它逐组等于完全背包的答案」）。
// ★ 而**官方样例正好挡住它**：`1 2` 那株草药能被采 70 次 ⇒ 输出 140，而答案是 3。

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

int main() {
    int T, m;
    if (!(cin >> T >> m)) return 0;
    vector<int> t(m), v(m);
    for (int i = 0; i < m; i++) cin >> t[i] >> v[i];

    vector<int> f(T + 1, 0);
    for (int i = 0; i < m; i++)
        for (int j = t[i]; j <= T; j++)              // ← 正序：同一株能采好几次
            f[j] = max(f[j], f[j - t[i]] + v[i]);

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

// P1048 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1048Count`      人看的版本
// `./p1048Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ DP ≡ 枚举所有子集（参照物离开「排序贪心」和「DP」两条路）；
//   ② ★★★ 第 20 章题单说「先用性价比贪心交一发，看着它 WA，**这一发 WA 值得挨**」——
//      量一量这一发**值多少分**：错的比例，以及错的时候平均差几个百分点；
//   ③ ★★★ 它的抓获率由什么决定：**不是 M，是「一株草药相对总时间有多大」**；
//   ④ ★★★ 和同一天那份 [P2240] 对照：**同一个贪心，能切就对、不能切就错** ——
//      把「能切」和「不能切」的答案差量出来；
//   ⑤ ★★ DP 循环写成正序那个 bug「**算了什么**」：它逐组等于**完全背包**的答案。

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

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

struct In { int T; vector<int> t, v; };

/** 正解：01 背包（倒序） */
static int dp01(const In& in) {
    vector<int> f(in.T + 1, 0);
    for (size_t i = 0; i < in.t.size(); i++)
        for (int j = in.T; j >= in.t[i]; j--) f[j] = max(f[j], f[j - in.t[i]] + in.v[i]);
    return f[in.T];
}
/** 错法三：正序 —— 它其实在解完全背包 */
static int dpFwd(const In& in) {
    vector<int> f(in.T + 1, 0);
    for (size_t i = 0; i < in.t.size(); i++)
        for (int j = in.t[i]; j <= in.T; j++) f[j] = max(f[j], f[j - in.t[i]] + in.v[i]);
    return f[in.T];
}
/** 完全背包的标准写法（拿来和上面那个 bug 逐组比） */
static int dpComplete(const In& in) {
    vector<int> f(in.T + 1, 0);
    for (int j = 1; j <= in.T; j++)
        for (size_t i = 0; i < in.t.size(); i++)
            if (in.t[i] <= j) f[j] = max(f[j], f[j - in.t[i]] + in.v[i]);
    return f[in.T];
}
/** 错法一：性价比贪心（整株拿） */
static int greedyRatio(const In& in) {
    int m = in.t.size();
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return (ll)in.v[x] * in.t[y] > (ll)in.v[y] * in.t[x];
    });
    int cap = in.T, ans = 0;
    for (int i : idx) if (in.t[i] <= cap) { cap -= in.t[i]; ans += in.v[i]; }
    return ans;
}
/** 错法二：按价值降序 */
static int greedyByV(const In& in) {
    int m = in.t.size();
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) { return in.v[x] > in.v[y]; });
    int cap = in.T, ans = 0;
    for (int i : idx) if (in.t[i] <= cap) { cap -= in.t[i]; ans += in.v[i]; }
    return ans;
}
/** ★ 同一批草药，如果**能切**（部分背包）：性价比贪心就是最优解。返回 ×100 的整数值 */
static ll fracBest100(const In& in) {
    int m = in.t.size();
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return (ll)in.v[x] * in.t[y] > (ll)in.v[y] * in.t[x];
    });
    ll cap = in.T, ans100 = 0;
    for (int i : idx) {
        if (in.t[i] <= cap) { cap -= in.t[i]; ans100 += 100LL * in.v[i]; }
        else { ans100 += 100LL * in.v[i] * cap / in.t[i]; cap = 0; break; }
    }
    return ans100;
}
/** 参照物：枚举所有子集 */
static int brute(const In& in) {
    int m = in.t.size(), best = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int st = 0, sv = 0;
        for (int i = 0; i < m; i++) if (mask >> i & 1) { st += in.t[i]; sv += in.v[i]; }
        if (st <= in.T) best = max(best, sv);
    }
    return best;
}

static In gen(mt19937& rng, int mHi, int tHi, int vHi) {
    In in;
    int m = (int)(rng() % (unsigned)mHi) + 1;
    in.T = (int)(rng() % (unsigned)tHi) + 1;
    in.t.resize(m); in.v.resize(m);
    for (int i = 0; i < m; i++) { in.t[i] = (int)(rng() % (unsigned)vHi) + 1; in.v[i] = (int)(rng() % (unsigned)vHi) + 1; }
    return in;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① DP ≡ 枚举所有子集 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            In in = gen(rng, 12, 200, 100);
            if (dp01(in) != brute(in)) bad++;
        }
        if (!CSV) printf("① DP vs 枚举所有子集：%d 组（M ≤ 12），不一致 %d 组\n", groups, bad);
        row("ref", {groups, bad});
    }

    /* ② 「这一发 WA」值多少分 */
    {
        mt19937 rng(1048u);
        int rounds = 300, badR = 0, badV = 0, badF = 0;
        long double lossR = 0, lossV = 0, worstR = 0;
        for (int r = 0; r < rounds; r++) {
            In in = gen(rng, 12, 200, 100);
            int ok = dp01(in);
            int gr = greedyRatio(in), gv = greedyByV(in);
            if (gr != ok) { badR++; long double d = ok ? (long double)(ok - gr) / ok : 0; lossR += d; worstR = max(worstR, d); }
            if (gv != ok) { badV++; lossV += ok ? (long double)(ok - gv) / ok : 0; }
            if (dpFwd(in) != ok) badF++;
        }
        ll avgR = (ll)(badR ? lossR / badR * 10000 + 0.5L : 0);      // 万分之几
        ll avgV = (ll)(badV ? lossV / badV * 10000 + 0.5L : 0);
        ll wR = (ll)(worstR * 10000 + 0.5L);
        if (!CSV) printf("② %d 轮：性价比贪心错 %d 次（错时平均只差 %.2f%%，最差 %.2f%%）；"
                         "按价值排错 %d 次（平均差 %.2f%%）；DP 正序错 %d 次\n",
                         rounds, badR, avgR / 100.0, wR / 100.0, badV, avgV / 100.0, badF);
        row("wa", {badR, avgR, wR, badV, avgV, badF});
    }

    /* ③ 抓获率的主语：一株草药相对总时间有多大 */
    {
        const int TS[] = {50, 200, 1000, 5000};      // T 的上限；草药 t ≤ 100 不变
        vector<ll> out;
        for (int tHi : TS) {
            mt19937 rng(tHi * 7919u + 5u);
            int bad = 0;
            long double loss = 0;
            for (int r = 0; r < 300; r++) {
                In in = gen(rng, 12, tHi, 100);
                int ok = dp01(in), gr = greedyRatio(in);
                if (gr != ok) { bad++; loss += ok ? (long double)(ok - gr) / ok : 0; }
            }
            ll avg = (ll)(bad ? loss / bad * 10000 + 0.5L : 0);
            out.push_back(bad); out.push_back(avg);
            if (!CSV) printf("③ T ≤ %5d（草药 t ≤ 100）：性价比贪心错 %d / 300，错时平均差 %.2f%%\n",
                             tHi, bad, avg / 100.0);
        }
        row("ratioT", out);
    }

    /* ④ ★★★ 同一个贪心：能切就对，不能切就错 */
    {
        mt19937 rng(2240u);
        int rounds = 300, fracBad = 0;
        long double gap = 0;
        for (int r = 0; r < rounds; r++) {
            In in = gen(rng, 12, 200, 100);
            ll fr100 = fracBest100(in);                 // 能切时的最优（= 性价比贪心）
            ll ok100 = 100LL * dp01(in);                // 不能切时的最优
            if (fr100 < ok100) fracBad++;               // 能切反而更差？不可能
            gap += ok100 ? (long double)(fr100 - ok100) / ok100 : 0;
        }
        ll avgGap = (ll)(gap / rounds * 10000 + 0.5L);
        if (!CSV) printf("④ 同一批草药：**能切**时的最优比**不能切**时平均高 %.2f%%；"
                         "「能切的最优 < 不能切的最优」出现 %d 次（应当是 0）\n", avgGap / 100.0, fracBad);
        row("frac", {avgGap, fracBad});
    }

    /* ⑤ 正序那个 bug 算了什么 */
    {
        mt19937 rng(999u);
        int rounds = 300, same = 0, diffFrom01 = 0;
        for (int r = 0; r < rounds; r++) {
            In in = gen(rng, 12, 200, 100);
            if (dpFwd(in) == dpComplete(in)) same++;
            if (dpFwd(in) != dp01(in)) diffFrom01++;
        }
        if (!CSV) printf("⑤ %d 轮：DP 正序那版 ≡ 完全背包的答案 %d 轮（逐组相等）；"
                         "而它和 01 背包不同 %d 轮\n", rounds, same, diffFrom01);
        row("fwd", {rounds, same, diffFrom01});
    }
    return 0;
}

// P1048 对拍生成器：`./p1048Gen <seed> [M 上限] [T 上限] [t、v 的上限]`
//   默认 `M ≤ 12`、`T ≤ 200`、`t, v ≤ 100` —— M 压在 12 是为了让 `2^M` 暴力当得了参照物。
//
// ★ 这道题真正该拧的旋钮不是 M，是 **T 相对 t 的比值**（页面第 ④ 步那张表）：
//   一株草药相对总时间越小，性价比贪心越接近最优（因为「装不下的零头」越小）；
//   草药大到一两株就占满时间，它就开始大幅出错。
//   ⇒ 这是[第 7 章 P1102](/sol/p1102/) 那条「不是『小数据』，是**比值**」的又一次。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mHi = argc > 2 ? atoi(argv[2]) : 12;
    int tHi = argc > 3 ? atoi(argv[3]) : 200;
    int vHi = argc > 4 ? atoi(argv[4]) : 100;
    mHi = max(1, min(100, mHi));
    tHi = max(1, min(1000, tHi));
    vHi = max(1, min(100, vHi));

    mt19937 rng(seed * 2654435761u + 48u);
    int m = (int)(rng() % (unsigned)mHi) + 1;
    int T = (int)(rng() % (unsigned)tHi) + 1;
    printf("%d %d\n", T, m);
    for (int i = 0; i < m; i++)
        printf("%u %u\n", (unsigned)(rng() % (unsigned)vHi) + 1, (unsigned)(rng() % (unsigned)vHi) + 1);
    return 0;
}