洛谷 P2240 【深基12.例1】部分背包问题

// P2240 错法一：按**总价值**从大到小排（不除以重量）
//
// 这是绝大多数人的第一反应：「先拿最值钱的那堆」。
// 它错在**没有把重量算进去** —— 一堆值 100 却重 25，和一堆值 60 只重 10，
// 后者每公斤 6 块、前者每公斤 4 块，背包装得下的重量是有限的。
//
// ★ 官方样例当场挡住它（230.00 vs 240.00）。

#include <bits/stdc++.h>
using namespace std;
struct Pile { int m, v; };

int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;
    vector<Pile> a(n);
    for (auto& p : a) cin >> p.m >> p.v;

    sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) { return x.v > y.v; });   // ← 只看价值

    double ans = 0; int cap = T;
    for (auto& p : a) {
        if (p.m <= cap) { ans += p.v; cap -= p.m; }
        else { ans += (double)p.v * cap / p.m; cap = 0; break; }
    }
    printf("%.2f\n", ans);
    return 0;
}

// P2240 错法二：按**重量**从小到大排（先拿轻的）
//
// 第二常见的第一反应：「轻的先拿，能多拿几堆」。
// 它同样漏了单位价值 —— 轻而不值钱的那堆会把容量白白吃掉。
//
// ★ 官方样例也挡住它（225.00 vs 240.00）。

#include <bits/stdc++.h>
using namespace std;
struct Pile { int m, v; };

int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;
    vector<Pile> a(n);
    for (auto& p : a) cin >> p.m >> p.v;

    sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) { return x.m < y.m; });   // ← 只看重量

    double ans = 0; int cap = T;
    for (auto& p : a) {
        if (p.m <= cap) { ans += p.v; cap -= p.m; }
        else { ans += (double)p.v * cap / p.m; cap = 0; break; }
    }
    printf("%.2f\n", ans);
    return 0;
}

// P2240【深基12.例1】部分背包问题 —— ★ 这一版就能 AC
//
// 题意：N 堆金币，第 i 堆重 m_i、值 v_i，**可以随意分割**（切开之后单位价格不变），
//       背包承重 T，问最多能拿走多少价值。输出实数，保留两位小数。
//
// ★ 关键一步：排序的关键字**不是题面直接给的**，是算出来的 —— **单位价值 v/m**。
//   交换论证（和第 19 章排队接水同一套）：设最优解里拿了 a 的一小块 δ 而没拿满 b，
//   且 b 的单位价值更高，那么把这 δ 换成 b 的 δ，重量不变、价值不降 ⇒ 贪心不吃亏。
//   ⚠ 这一步在 01 背包里**不成立**（第 23 章）—— 那儿不能切，换不过去。
//
// ⚠ 三个和贪心无关的地方（页面上各量了一个）：
//   ① **比较别用除法**：`v1/m1 > v2/m2` 写成交叉相乘 `v1*m2 > v2*m1` 就没有浮点了。
//      ★ 这道题的数据小（v, m ≤ 100），实测两种写法 20 万组一次不差 ——
//        **但那是量出来的，不是想当然的**（页面第 ⑤ 步）。
//   ② **最后那一刀要用浮点**：`v * cap / m` 全用 int 会把小数截掉（页面第 ④ 步，样例放过它）。
//   ③ **可能装不满**：总重量小于 T 时全部拿走，循环自然就结束了 —— 别硬凑 T。

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

struct Pile { int m, v; };

int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;
    vector<Pile> a(n);
    for (auto& p : a) cin >> p.m >> p.v;

    // 按单位价值从高到低：v1/m1 > v2/m2  ⇔  v1*m2 > v2*m1（★ 全整数，没有浮点）
    sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) {
        return (long long)x.v * y.m > (long long)y.v * x.m;
    });

    double ans = 0;
    int cap = T;
    for (auto& p : a) {
        if (p.m <= cap) { ans += p.v; cap -= p.m; }        // 整堆装得下
        else { ans += (double)p.v * cap / p.m; cap = 0; break; }   // ★ 最后一刀，必须浮点
    }
    printf("%.2f\n", ans);
    return 0;
}

// P2240 错法三：排序全对，最后那一刀用**整数除法**
//
// `p.v * cap / p.m` 三个都是 int ⇒ 先算 `v*cap`（还好，≤ 100 × 1000 = 10⁵ 不溢出），
// 再**整除** m —— 小数部分直接没了。
//
// ★★ 而官方样例**放过了它**：那一刀正好是 `100 × 20 / 25 = 80`，**整除**。
//   ⇒ 这一页三个错法里，样例挡住的两个都是「每一组都错」的，
//     放过的这一个是「只有除不尽才错」的 —— 和同一天
//     [P1223](/sol/p1223/) 量出来的规律一模一样：
//     **官方样例是个「一测就死」的过滤器，隐蔽的 bug 天然通过。**

#include <bits/stdc++.h>
using namespace std;
struct Pile { int m, v; };

int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;
    vector<Pile> a(n);
    for (auto& p : a) cin >> p.m >> p.v;

    sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) {
        return (long long)x.v * y.m > (long long)y.v * x.m;
    });

    double ans = 0; int cap = T;
    for (auto& p : a) {
        if (p.m <= cap) { ans += p.v; cap -= p.m; }
        else { ans += p.v * cap / p.m; cap = 0; break; }    // ← 三个 int，整除
    }
    printf("%.2f\n", ans);
    return 0;
}

// P2240 的**第二个算法**：容量上的动态规划 —— 它不是用来交的，是用来当参照物的
//
// ★ 这道题的贪心只有五行，而「五行代码对不对」恰恰最难验：
//   三个错法都只差一个排序关键字，看上去都一样合理。
//   ⇒ 需要一个**不排序**的参照物。
//
// 造法：题面里 `m_i` 和 `T` 都是整数，而贪心只会切**一刀**、切的量也是整数
//   ⇒ 把每堆看成 `m_i` 个「重 1、值 v_i/m_i」的小块，问题就变成一个**有界背包**：
//     `f[c] = 用容量 c 最多能拿多少价值`，`f[c] = max(f[c], f[c-k] + k·v_i/m_i)`。
//   它一次排序都没有，和贪心的思路毫无关系。
//   复杂度 `O(N T m)`，顶格 100 × 1000 × 100 = 10⁷，跑得动。
//
// ⚠ 它用 long double 累加 ⇒ 只能当**参照物**，不适合当交上去的答案
//   （而这道题真正的答案是个有理数 —— 页面第 ⑥ 步专门讲这件事）。

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

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

    vector<long double> f(T + 1, 0.0L);
    for (int i = 0; i < n; i++) {
        long double unit = (long double)v[i] / m[i];
        vector<long double> g = f;
        for (int c = 0; c <= T; c++) {
            int lim = min(m[i], c);
            for (int k = 1; k <= lim; k++)
                g[c] = max(g[c], f[c - k] + k * unit);
        }
        f.swap(g);
    }
    long double best = 0;
    for (int c = 0; c <= T; c++) best = max(best, f[c]);
    printf("%.2f\n", (double)best);
    return 0;
}

// P2240 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p2240Count`      人看的版本
// `./p2240Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ 三方一致：贪心 / 容量 DP / **精确有理数**，三条路逐组比；
//   ② ★ 三个错法各被抓多少 —— 顺带量「整数除法」那个的**两层触发条件**；
//   ③ ★★ 「`v1/m1 > v2/m2` 会不会掉精度」：在题面范围里**穷举**着比，不猜；
//   ④ ★★★ 这道题的答案是个**有理数**，而输出只留两位小数 ——
//      「精确值四舍五入」和 `printf("%.2f", double)` **不是同一件事**；
//   ⑤ ★ 「装不满」的输入占多少（题面没保证装得满）。

#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 Pile { int m, v; };

/** 贪心（正解那份的逻辑），同时给出**精确有理数** N/D 和 double 值 */
static void greedyExact(vector<Pile> a, int T, ll& N, ll& D, double& dv, bool* cut = nullptr) {
    sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) {
        return (ll)x.v * y.m > (ll)y.v * x.m;
    });
    ll whole = 0; int cap = T; ll pn = 0, pd = 1;
    if (cut) *cut = false;
    for (auto& p : a) {
        if (p.m <= cap) { whole += p.v; cap -= p.m; }
        else { pn = (ll)p.v * cap; pd = p.m; if (cut) *cut = (pn % pd != 0); cap = 0; break; }
    }
    N = whole * pd + pn; D = pd;
    dv = (double)whole + (pd > 1 || pn ? (double)pn / pd : 0.0);
}

/** 精确值四舍五入到两位小数（半进位向上），返回「多少分」 */
static ll centsRoundHalfUp(ll N, ll D) {
    ll q = 100 * N / D, r = 100 * N % D;
    if (2 * r >= D) q++;
    return q;
}
static string cents2str(ll c) {
    char buf[64];
    snprintf(buf, sizeof(buf), "%lld.%02lld", c / 100, c % 100);
    return buf;
}
static string printf2(double x) {
    char buf[64];
    snprintf(buf, sizeof(buf), "%.2f", x);
    return buf;
}

/** 三个错法 */
static string byKey(vector<Pile> a, int T, int kind) {
    if (kind == 0) sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) { return x.v > y.v; });
    else if (kind == 1) sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) { return x.m < y.m; });
    else sort(a.begin(), a.end(), [](const Pile& x, const Pile& y) { return (ll)x.v * y.m > (ll)y.v * x.m; });
    double ans = 0; int cap = T;
    for (auto& p : a) {
        if (p.m <= cap) { ans += p.v; cap -= p.m; }
        else {
            if (kind == 2) ans += (double)(p.v * cap / p.m);      // ← 整数除法
            else ans += (double)p.v * cap / p.m;
            cap = 0; break;
        }
    }
    return printf2(ans);
}

/** 容量上的有界背包（不排序，和贪心思路无关） */
static double dpRef(const vector<Pile>& a, int T) {
    vector<long double> f(T + 1, 0.0L);
    for (auto& p : a) {
        long double unit = (long double)p.v / p.m;
        vector<long double> g = f;
        for (int c = 0; c <= T; c++) {
            int lim = min(p.m, c);
            for (int k = 1; k <= lim; k++) g[c] = max(g[c], f[c - k] + k * unit);
        }
        f.swap(g);
    }
    long double best = 0;
    for (int c = 0; c <= T; c++) best = max(best, f[c]);
    return (double)best;
}

static vector<Pile> gen(mt19937& rng, int n, int hi) {
    vector<Pile> a(n);
    for (int i = 0; i < n; i++) a[i] = {(int)(rng() % (unsigned)hi) + 1, (int)(rng() % (unsigned)hi) + 1};
    return a;
}

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

    /* ① 三方一致（贪心 / DP / 精确有理数） */
    {
        mt19937 rng(20260829u);
        int groups = 0, badDp = 0, badExact = 0;
        for (int rep = 0; rep < 200; rep++, groups++) {
            int n = (int)(rng() % 12) + 1, T = (int)(rng() % 60) + 1;
            vector<Pile> a = gen(rng, n, 20);
            ll N, D; double dv;
            greedyExact(a, T, N, D, dv);
            if (printf2(dpRef(a, T)) != printf2(dv)) badDp++;
            if (fabsl((long double)N / D - (long double)dv) > 1e-9L) badExact++;
        }
        if (!CSV) printf("① 三方一致 %d 组：贪心 vs 容量 DP 不同 %d 组；贪心 vs 精确有理数不同 %d 组\n",
                         groups, badDp, badExact);
        row("three", {groups, badDp, badExact});
    }

    /* ② 三个错法的抓获率（顶格随机） */
    {
        mt19937 rng(4242u);
        int bv = 0, bm = 0, bi = 0, cutRounds = 0, cutCaught = 0;
        for (int r = 0; r < 300; r++) {
            int n = (int)(rng() % 100) + 1, T = (int)(rng() % 1000) + 1;
            vector<Pile> a = gen(rng, n, 100);
            ll N, D; double dv; bool cut;
            greedyExact(a, T, N, D, dv, &cut);
            string ok = printf2(dv);
            if (byKey(a, T, 0) != ok) bv++;
            if (byKey(a, T, 1) != ok) bm++;
            bool caught = byKey(a, T, 2) != ok;
            if (caught) bi++;
            if (cut) { cutRounds++; if (caught) cutCaught++; }
        }
        if (!CSV) printf("② 顶格随机 300 轮：按总价值排错 %d 次，按重量排错 %d 次，整数除法那版错 %d 次\n"
                         "   （其中「最后一刀除不尽」的有 %d 轮，这 %d 轮里被抓 %d 轮）\n",
                         bv, bm, bi, cutRounds, cutRounds, cutCaught);
        row("wrong", {bv, bm, bi, cutRounds, cutCaught});
    }

    /* ③ 浮点比较 vs 交叉相乘：题面范围内穷举 */
    {
        ll pairs = 0, diff = 0;
        for (int v1 = 1; v1 <= 100; v1++)
            for (int m1 = 1; m1 <= 100; m1++)
                for (int v2 = 1; v2 <= 100; v2++)
                    for (int m2 = 1; m2 <= 100; m2++) {
                        pairs++;
                        bool a = (double)v1 / m1 > (double)v2 / m2;
                        bool b = (ll)v1 * m2 > (ll)v2 * m1;
                        if (a != b) diff++;
                    }
        /* ⚠ 自检：上面那个 0 有可能是「这一段根本没在量东西」。
           换一个**必须不为 0** 的比较：把除法那边写成 `>=`，它和 `>` 只会在
           **两边单位价值正好相等**的时候给出不同答案 ——
           而「相等的对有多少」可以用整数独立数一遍。两个数相等 ⇒ 这个穷举确实是活的。 */
        ll diffGe = 0, ties = 0;
        for (int v1 = 1; v1 <= 100; v1++)
            for (int m1 = 1; m1 <= 100; m1++)
                for (int v2 = 1; v2 <= 100; v2++)
                    for (int m2 = 1; m2 <= 100; m2++) {
                        bool a = (double)v1 / m1 >= (double)v2 / m2;
                        bool b = (ll)v1 * m2 > (ll)v2 * m1;
                        if (a != b) diffGe++;
                        if ((ll)v1 * m2 == (ll)v2 * m1) ties++;
                    }
        if (!CSV) printf("③ 穷举 %lld 组 (v1,m1,v2,m2)（题面范围 1..100）：除法比较和交叉相乘结论不同 %lld 组\n"
                         "   ⚠ 自检（证明这段不是空壳）：把除法那边改成 >=，不同 %lld 组；\n"
                         "      而「单位价值正好相等」的对用整数独立数出来是 %lld 组 —— 两个数必须相等\n",
                         pairs, diff, diffGe, ties);
        row("cmp", {pairs, diff, diffGe, ties});
    }

    /* ④ ★★★ 答案是有理数：精确四舍五入 vs printf("%.2f", double) */
    {
        mt19937 rng(31337u);
        int rounds = 200000, diff = 0;
        for (int r = 0; r < rounds; r++) {
            int n = (int)(rng() % 5) + 1, T = (int)(rng() % 40) + 1;
            vector<Pile> a = gen(rng, n, 100);
            ll N, D; double dv;
            greedyExact(a, T, N, D, dv);
            string exact = cents2str(centsRoundHalfUp(N, D));
            if (exact != printf2(dv)) diff++;
        }
        if (!CSV) printf("④ 随机 %d 组：精确值四舍五入 和 printf(\"%%.2f\", double) 打出的字符串不同 %d 组\n",
                         rounds, diff);
        // 那个能手算的例子：一堆 (m=8, v=1)，T=1 ⇒ 精确答案正好是 0.125
        {
            vector<Pile> a = {{8, 1}};
            ll N, D; double dv;
            greedyExact(a, 1, N, D, dv);
            string exact = cents2str(centsRoundHalfUp(N, D));
            string byPrintf = printf2(dv);
            if (!CSV) printf("   例：`1 1 / 8 1`（答案正好 0.125）—— 精确四舍五入 %s，printf 打出 %s\n",
                             exact.c_str(), byPrintf.c_str());
            row("tie", {N, D, exact == "0.13" ? 13 : 0, byPrintf == "0.12" ? 12 : 0});
        }
        row("round", {rounds, diff});
    }

    /* ⑤ 装不满的输入占多少 */
    {
        mt19937 rng(9001u);
        int notFull = 0;
        for (int r = 0; r < 300; r++) {
            int n = (int)(rng() % 100) + 1, T = (int)(rng() % 1000) + 1;
            vector<Pile> a = gen(rng, n, 100);
            ll tot = 0;
            for (auto& p : a) tot += p.m;
            if (tot < T) notFull++;
        }
        if (!CSV) printf("⑤ 顶格随机 300 轮：总重量小于 T（装不满，全部拿走）的有 %d 轮\n", notFull);
        row("notFull", {notFull});
    }
    return 0;
}

// P2240 对拍生成器：`./p2240Gen <seed> [N 上限] [值域上限] [T 上限]`
//   默认 `N ≤ 100`、`m, v ≤ 100`、`T ≤ 1000` —— ★ 就是题面顶格。
//
// ★ 这道题的输入空间很小（题面自己就把三个上限写死在描述里），
//   所以生成器没什么可拧的旋钮 —— 唯一值得拧的是**值域**：
//   `m, v` 的上限越小，单位价值撞在一起的越多，「排序关键字算错」那几个错法反而**更难**现形。

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

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

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