洛谷 P1049 [NOIP 2001 普及组] 装箱问题

// P1049 错法一：贪心 —— 体积从大到小，能塞就塞
//
// 这是大多数人的第一反应，而且**官方样例放过了它**：
//   V = 24，物品 8 3 12 7 9 7 ⇒ 从大到小是 12 9 8 7 7 3，
//   塞 12（剩 12）、塞 9（剩 3）、8 塞不下、7 塞不下、7 塞不下、塞 3（剩 0）⇒ 输出 0，和正解一样。
//
// ⚠ 而它是错的，最小的反例只要三件物品：
//     V = 10，物品 6 5 5  ⇒  贪心先拿 6，剩 4，两个 5 都塞不下 ⇒ 剩 4
//                            正解 5 + 5 = 10          ⇒ 剩 0
//
// ★ 「先拿大的」错在哪：它把「装得尽量满」偷换成了「先把大的安顿好」，
//   而背包问题里**一件物品该不该拿，取决于剩下的空间还能不能被别的物品配平** ——
//   这正是第 20 章那一整章在讲的事（贪心要证，不能猜）。

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

int main() {
    int V, n;
    if (!(cin >> V >> n)) return 0;
    vector<int> v(n);
    for (int& x : v) cin >> x;

    sort(v.begin(), v.end(), greater<int>());
    int left = V;
    for (int x : v)
        if (x <= left) left -= x;             // 能塞就塞

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

// P1049 [NOIP 2001 普及组] 装箱问题 —— ★ 这一版就能 AC
//
// 题意：箱子容量 V，n 个物品各有一个体积，任取若干件装进去（也可以不取），
//       问箱子**剩余空间**最小是多少。
//
// ★★ 这道题的第一道门槛不在算法，在**读题**：它给的物品**只有体积，没有价值**。
//   而 01 背包的模板要「体积」和「价值」两样东西。缺的那样从哪儿来？
//
//   **把体积同时当成价值。**
//
//   一句话的道理：要「剩余空间最小」，就是要「装进去的体积之和最大」——
//   而「装进去的体积之和」正好就是「选中物品的体积和」。
//   ⇒ 于是 w[i] = v[i] = 体积，跑一遍标准 01 背包，答案是 `V - f[V]`。
//
// ⚠ 别忘了最后那一下减法：f[V] 是**装进去多少**，题目问的是**剩下多少**。
//   （这一下漏掉的话官方样例当场就会打出 24 而不是 0 —— 见解析页第 ⑥ 步。）
//
// 复杂度 O(nV) = 30 × 20000 = 6 × 10^5 —— 而 2^n 是 1.07 × 10^9，差 1789 倍。

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

int main() {
    int V, n;
    if (!(cin >> V >> n)) return 0;
    vector<int> v(n);
    for (int& x : v) cin >> x;

    vector<int> f(V + 1, 0);                  // f[j] = 容量恰好 j 时，最多能装进去的体积
    for (int i = 0; i < n; i++)
        for (int j = V; j >= v[i]; j--)       // ★ 倒序：每件最多用一次（第 23 章第 ⑧ 步）
            f[j] = max(f[j], f[j - v[i]] + v[i]);

    cout << V - f[V] << "\n";                 // ⚠ 问的是剩余空间
    return 0;
}

// P1049 错法二：一维写成正序 —— 它精确地解了另一道题
//
// 把第 23 章那句「倒序」写成正序，这一版就变成了**完全背包**：
// 每一捆……不对，每一件物品可以被**重复装进箱子任意多次**。
//
// ⇒ 于是它算出来的「装进去的体积」只会更大（或相等），剩余空间只会更小（或相等）。
//   **它不是随机地错，它恒等于「每件物品有无限多个」那道题的答案。**
//   （解析页第 ⑤ 步把这句话量成了 300 组逐组相等。）
//
// ★ 而在这道题上，这个 bug 有一个白送的推论：
//   只要**存在某件物品的体积能整除某段空隙**，正序就可能把箱子塞得更满 ——
//   最极端的情形是有一件体积为 1 的物品，那它一定能把箱子塞满、输出 0。

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

int main() {
    int V, n;
    if (!(cin >> V >> n)) return 0;
    vector<int> v(n);
    for (int& x : v) cin >> x;

    vector<int> f(V + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = v[i]; j <= V; j++)       // ⚠ 正序 —— 同一件物品会被反复拿
            f[j] = max(f[j], f[j - v[i]] + v[i]);

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

// P1049 错法三：算对了，但**忘了最后那一下减法**
//
// f[V] 是「最多能装进去多少体积」，而题目问的是「箱子还剩多少空间」。
// 这一版把 f[V] 直接打了出来。
//
// ★ 它是这一页四个错法里**唯一一个被官方样例当场挡住**的：
//   样例答案是 0，而它打出 24。
//   ⇒ 又一次「[官方样例是个『一测就死』的过滤器](/sol/p1223/)」：
//     它挡住的都是「每一组都错」的错法，放过的都是「偶尔才错」的。
//     而真正让你 WA 在第 7 个点上的，恰恰是后一种。

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

int main() {
    int V, n;
    if (!(cin >> V >> n)) return 0;
    vector<int> v(n);
    for (int& x : v) cin >> x;

    vector<int> f(V + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + v[i]);

    cout << f[V] << "\n";                     // ⚠ 打的是「装进去多少」，不是「剩下多少」
    return 0;
}