01 背包

// 01 背包 —— 2ⁿ 枚举子集：每件物品「拿 / 不拿」，所有组合都试
//
// ⚠ **第 23 章也直接用这一份**（那一章 import 的就是这个文件），拿它当 01 背包 DP 的
//   对拍标准答案，以及「2ⁿ vs O(nW)」那张耗时表的左半边。
//   ⇒ 改这份代码要连第 23 章一起看，那边还有一张跟着它跑出来的表。
//
// 这是这一章第二个对拍的标准答案。它慢，但它绝对不会错 ——
// 因为它根本没有「想法」，只是把所有可能都列了一遍（接第 3 章的二进制枚举）。
//
// 题意：n 件物品，第 i 件价值 v[i]、重量 w[i]，每件**最多拿一件**（不能切开）。
//       背包最多装 W 的重量。求能装走的最大总价值。
//
// 输入：第一行 n W，接下来 n 行每行两个数 v w
// 输出：最大总价值
//
// n ≤ 20 左右，再大就跑不完了。真正的解法是第 23 章的 DP，
// 但这一章我们只需要它当尺子 —— 用来量贪心到底差多少。

#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), w(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    long long best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        long long sw = 0, sv = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) { sw += w[i]; sv += v[i]; }
        if (sw <= W) best = max(best, sv);
    }

    cout << best << "\n";
    return 0;
}

// 01 背包 —— 二维 DP，最老实的写法
//
// 为什么先写这一份：一维那份（fast.cpp）是从它压出来的。
// 直接背一维的三行代码，你会背错倒序；但如果先把二维写明白，
// 倒序就不是「规定」，而是压缩之后的必然结果。**先二维，再压。**
//
// 状态：f[i][j] = 只在前 i 件物品里挑，背包容量恰好不超过 j 时的最大价值
// 转移：第 i 件物品只有两种命运 ——
//   不拿：f[i][j] = f[i-1][j]
//   拿  ：f[i][j] = f[i-1][j - w[i]] + v[i]      （前提 j >= w[i]）
//   取两者的较大值。
// 边界：f[0][j] = 0（一件都不挑，价值 0）
// 答案：f[n][W]
//
// ★ 注意转移右边两个式子的第一维**都是 i-1**。
//   这是这一章后面所有事情的根源：**第 i 件物品只能从「还没考虑它」的那一行取值**，
//   否则它就可能被拿第二次。
//
// 输入：第一行 n W，接下来 n 行每行两个数 v w（和第 20 章 knapBrute.cpp 完全一致，方便对拍）
// 输出：最大总价值
//
// 复杂度 O(nW) 时间、O(nW) 空间。n = 100、W = 10000 时是 100 万格，随便跑；
// 但 n = 1000、W = 10^5 就是 1 亿格 × 8 字节 = 800 MB，**空间先炸** —— 这就是要压成一维的原因。

#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];

    // f[i][j]，下标从 1 开始（第 0 行全是 0，就是「一件都不挑」）
    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++) {
            f[i][j] = f[i - 1][j];                                  // 不拿第 i 件
            if (j >= w[i])                                          // 拿得下才谈「拿」
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);  // ★ 右边是 i-1 行
        }
    }

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

// 01 背包 —— 一维倒序，竞赛里就写这三行
//
// 从 roll.cpp 再砍一刀：两行也别留了，只留一行，原地改。
//
//   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]);
//
// ★★ 这一章的关键一步：**第二层循环必须倒着写。**
//
// 为什么。把一维的 f 想成「上一行和这一行挤在同一块内存里」：
// 当你正在算 f[j] 的时候，f[j - w[i]] 这一格到底是「上一行的」还是「这一行的」？
//
//   倒序（j 从大到小）：j - w[i] < j，而比 j 小的格子**这一轮还没轮到**，
//                       所以读到的一定是上一行的值 —— 和 dp2.cpp 的 f[i-1][j-w[i]] 一模一样。✓
//   正序（j 从小到大）：j - w[i] < j，而比 j 小的格子**这一轮刚刚被改过**，
//                       读到的是这一行的值 f[i][j-w[i]] —— 那一格里可能已经装了第 i 件物品，
//                       于是第 i 件物品被拿了第二次、第三次…… ✗
//
// 而且正序**不会报错、不会崩、不会警告**，只是安静地给你一个偏大的答案。
// （它其实精确地解了另一道题 —— 见 complete.cpp。）
//
// 另外两个细节：
//   ① 循环写成 `j >= w[i]` 而不是 `j >= 0`，省掉了 j < w[i] 时的判断（那些格子必然维持原值）。
//   ② f 一定要开在循环外面并且**只初始化一次**：f[j] 的含义是「前 i 件物品、容量 j」，
//      每一轮是在上一轮的基础上继续，不是重来。
//
// 输入输出同 dp2.cpp。复杂度 O(nW) 时间、O(W) 空间。

#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;
}

// 把一维数组的每一步都打出来：倒序 vs 正序，逐行对照
//
// 为什么要有这份代码：光看最终答案「14 和 18」，你只知道正序错了，不知道它错在哪一格。
// 这份代码把每处理完一件物品之后的整个 f 数组打出来，
// 两边并排一看就明白：**正序那边，某些格子在同一轮里被同一件物品填了不止一次。**
//
// 默认数据（也是正文和动画用的那组）：
//   n = 4，W = 9，物品 (v,w) = (6,3) (5,4) (8,5) (2,2)
//   正确答案 14（拿第 1、3 件，重量 3+5=8）
//   正序答案 18（第 1 件被拿了三次：3×3=9 正好装满，3×6=18）
//
// 注意看正序那边第一行就已经错了：只处理了第一件物品，f[9] 就变成了 18。
// 一件物品，价值 6，却贡献了 18 —— 拿了三次。
//
// 输出的每一行是 f[0..W]。check-viz 会拿它和动画里的数组**逐行**比对，
// 不只比最后那个答案（否则「答案对了但中间过程画的是另一回事」就查不出来）。
//
// 输入：同 dp2.cpp（不给输入就用上面那组默认数据）

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

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

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

    if (cin >> n >> W) {
        v.resize(n + 1);
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    } else {
        n = 4;
        W = 9;
        v = {0, 6, 5, 8, 2};
        w = {0, 3, 4, 5, 2};
    }

    cout << "物品：";
    for (int i = 1; i <= n; i++) cout << "(v=" << v[i] << " w=" << w[i] << ") ";
    cout << "  容量 W = " << W << "\n";

    for (int pass = 0; pass < 2; pass++) {
        bool down = (pass == 0);
        cout << "\n" << (down ? "倒序（正确）" : "正序（错误）") << "\n";

        vector<long long> f(W + 1, 0);
        cout << "初始    ：";
        for (long long j = 0; j <= W; j++) cout << f[j] << " \n"[j == W];

        for (int i = 1; i <= n; i++) {
            if (down)
                for (long long j = W; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
            else
                for (long long j = w[i]; j <= W; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);

            cout << "第 " << i << " 件后：";
            for (long long j = 0; j <= W; j++) cout << f[j] << " \n"[j == W];
        }
        cout << "答案 = " << f[W] << "\n";
    }
    return 0;
}

// 「恰好装满」的变体 —— 01 背包排第二的坑，而且它只藏在**初始化**里
//
// 题目一改成「必须把背包**正好**装满，求最大价值（装不满输出 -1）」，
// 转移方程一个字都不用改，要改的只有 f 的初值：
//
//   不要求装满：f[j] = 0        —— 「容量 j，什么都不装」是一个合法状态，价值 0
//   要求装满  ：f[0] = 0，其余 f[j] = -∞
//                              —— 「容量 j 正好装满」在还没放东西时**根本不存在**，
//                                 用 -∞ 表示「这个状态不可达」
//
// ★ 一句话记法：**初值是在回答「这个状态一开始存不存在」。**
//   转移只会从存在的状态转出去（-∞ 加多少还是负的，永远抢不过别人），
//   于是不可达就自动传播下去了。
//   同一个套路还会用在「方案数」（初值 f[0]=1 其余 0）、「最小价值」（初值 +∞）上。
//
// 这份代码同时用两种完全不同的思路算这道题，自己跟自己对拍：
//   ① 2ⁿ 枚举子集（n ≤ 20），挑出重量正好等于 W 的组合
//   ② DP，初值 -∞
// check-viz 会验这两行 300 组数据一模一样 —— **不同思路才能验出想法错误**（第 20 章那条规矩）。
//
// 默认数据上有个刚好能说明问题的巧合：
//   n=4 W=9 物品 (6,3)(5,4)(8,5)(2,2) → 不要求装满是 14，要求正好装满只有 13。
//   14 那个方案（第 1、3 件）重量是 8，差一格没装满。
//
// 输入输出：输入同 dp2.cpp；输出两行，分别是两种思路算出的答案（装不满都输出 -1）

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

const long long NEG = LLONG_MIN / 4;    // 不用 LLONG_MIN，否则加 v[i] 会溢出

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), w(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    /* ① 2ⁿ 枚举子集：只看重量正好 = W 的那些组合 */
    long long bruteBest = -1;
    if (n <= 20) {
        for (int mask = 0; mask < (1 << n); mask++) {
            long long sw = 0, sv = 0;
            for (int i = 0; i < n; i++)
                if (mask >> i & 1) { sw += w[i]; sv += v[i]; }
            if (sw == W) bruteBest = max(bruteBest, sv);
        }
    }

    /* ② DP：转移和 fast.cpp 一字不差，只有初值不同 */
    vector<long long> f(W + 1, NEG);
    f[0] = 0;                                        // ★ 唯一一个「一开始就存在」的状态
    for (int i = 0; i < n; i++)
        for (long long j = W; j >= w[i]; j--)
            if (f[j - w[i]] > NEG)                   // 不可达的状态不往外转移
                f[j] = max(f[j], f[j - w[i]] + v[i]);
    long long dpBest = (f[W] > NEG) ? f[W] : -1;

    cout << "2ⁿ 枚举（恰好装满）：" << bruteBest << "\n";
    cout << "DP（f 初值 -∞）    ：" << dpBest << "\n";
    return 0;
}

// 01 背包 —— 不只要最大价值，还要说出**到底拿了哪几件**
//
// ★ 用的是第 22 章 path.cpp 那个通用套路的背包版，但有一处不同，值得单独讲：
//
//   LIS 那题记的是 pre[i]（从哪个 j 转移来的）；
//   背包这里**什么都不用记** —— 因为二维表本身就把历史留住了。
//   从 f[n][W] 出发倒着走：
//       f[i][j] == f[i-1][j]  →  第 i 件没拿，跳到 (i-1, j)
//       否则                  →  第 i 件拿了，跳到 (i-1, j - w[i])
//
// ⚠ 而这正是「要输出方案就不能用一维」的原因：
//   一维数组把中间过程全覆盖掉了，没有历史可以回溯。
//   **要方案 → 老老实实开二维表。** 这是所有 DP 的通用规律，不是背包特有的。
//
// 相同价值的方案可能有好几种，这里给的是「上面那条判断优先算作没拿」得到的那一条。
//
// 输出：第一行最大价值，第二行选中的物品编号（1 基，升序），第三行它们的总重量
//
// check-viz 对这份代码做的是**硬验证**：
//   ① 编号不重复、都在 1..n 范围内
//   ② 总重量 ≤ W
//   ③ 价值之和正好等于第一行那个最大价值
// 只验第一行的话，「价值对了但方案是编的」这种 bug 是抓不出来的。

#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++) {
            f[i][j] = f[i - 1][j];
            if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
        }

    vector<int> take;
    long long j = W, sumW = 0;
    for (int i = n; i >= 1; i--) {
        if (f[i][j] == f[i - 1][j]) continue;       // 这一件没拿（并列时算作没拿）
        take.push_back(i);
        sumW += w[i];
        j -= w[i];
    }
    reverse(take.begin(), take.end());              // 倒着走出来的，翻回去

    cout << f[n][W] << "\n";
    for (size_t k = 0; k < take.size(); k++) cout << take[k] << " \n"[k + 1 == take.size()];
    if (take.empty()) cout << "\n";                 // 一件都没拿也要占一行，方便解析
    cout << sumW << "\n";
    return 0;
}

// 01 背包 —— 一维倒序，竞赛里就写这三行
//
// 从 roll.cpp 再砍一刀：两行也别留了，只留一行，原地改。
//
//   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]);
//
// ★★ 这一章的关键一步：**第二层循环必须倒着写。**
//
// 为什么。把一维的 f 想成「上一行和这一行挤在同一块内存里」：
// 当你正在算 f[j] 的时候，f[j - w[i]] 这一格到底是「上一行的」还是「这一行的」？
//
//   倒序（j 从大到小）：j - w[i] < j，而比 j 小的格子**这一轮还没轮到**，
//                       所以读到的一定是上一行的值 —— 和 dp2.cpp 的 f[i-1][j-w[i]] 一模一样。✓
//   正序（j 从小到大）：j - w[i] < j，而比 j 小的格子**这一轮刚刚被改过**，
//                       读到的是这一行的值 f[i][j-w[i]] —— 那一格里可能已经装了第 i 件物品，
//                       于是第 i 件物品被拿了第二次、第三次…… ✗
//
// 而且正序**不会报错、不会崩、不会警告**，只是安静地给你一个偏大的答案。
// （它其实精确地解了另一道题 —— 见 complete.cpp。）
//
// 另外两个细节：
//   ① 循环写成 `j >= w[i]` 而不是 `j >= 0`，省掉了 j < w[i] 时的判断（那些格子必然维持原值）。
//   ② f 一定要开在循环外面并且**只初始化一次**：f[j] 的含义是「前 i 件物品、容量 j」，
//      每一轮是在上一轮的基础上继续，不是重来。
//
// 输入输出同 dp2.cpp。复杂度 O(nW) 时间、O(W) 空间。

#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;
}