数据生成器 (Generator)

生成器包含小规模数据、背包塞不下的数据、物品价值很高但重量很大的数据等。

请保存为 gen_knapsack.cpp 并运行。

/**
 * Project: The Cell's Energy Budget (Knapsack Data Generator)
 * Author: Isaac Asimov (AI)
 */

#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int c, n;
        cin >> c >> n;
        vector<int> dp(c + 1, 0);

        for (int i = 0; i < n; i++) {
            int w, v;
            cin >> w >> v;
            for (int j = c; j >= w; j--) {
                dp[j] = max(dp[j], dp[j - w] + v);
            }
        }
        cout << dp[c] << endl;
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int c, n;

    if (case_id == 1) {
        // 样例 1
        c = 10; n = 4;
        fout << c << " " << n << endl;
        fout << "2 3\n3 4\n4 5\n5 6" << endl;
        fout.close();
        return;
    }

    // 规模控制
    if (case_id <= 3) {
        c = rand_int(10, 50);
        n = rand_int(5, 10);
    } else if (case_id <= 7) {
        c = rand_int(100, 500);
        n = rand_int(20, 50);
    } else {
        c = 1000;
        n = 100;
    }

    fout << c << " " << n << endl;

    for (int i = 0; i < n; i++) {
        int w, v;
        if (case_id == 2) {
            // 样例 2 复现：所有物品都买不起
            w = c + rand_int(1, 10);
            v = rand_int(1, 100);
        } 
        else if (case_id == 5) {
            // 性价比陷阱：重量小价值低 vs 重量大价值极高
            if (i % 2 == 0) { w = rand_int(1, 5); v = rand_int(1, 5); }
            else { w = rand_int(c/2, c); v = rand_int(100, 200); }
        }
        else {
            // 常规随机
            // 物品重量在 1 到 C 之间随机
            w = rand_int(1, c);
            // 偶尔生成一些很小的物品
            if (rand_int(1, 100) < 30) w = rand_int(1, c/5 + 1);
            
            v = rand_int(1, 1000);
        }
        fout << w << " " << v << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Knapsack Data ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

阿西莫夫的解题指南

这是动态规划中最基础、最重要的模型。

1. 状态定义

定义一维数组 dp[j]。 含义：当细胞拥有 $j$ 单位的 ATP 时，能获得的最大生存价值。

2. 状态转移方程

对于第 $i$ 个任务（消耗 $w$，价值 $v$），我们倒序遍历 ATP 预算 $j$（从 $C$ 到 $w$）：

• dp[j]（不选这个任务）：维持原样。
• dp[j-w] + v（选这个任务）：腾出 $w$ 的空间，加上 $v$ 的价值。

为什么是一维数组？ 这就好比细胞只有一个“能量槽”。我们从大到小更新，是为了保证在计算 dp[j] 时，用到的 dp[j-w] 还是上一轮（即还没考虑当前任务时）的状态，从而确保每个任务只被计算一次（0/1 背包的特征）。

C++ 标准解答 (NOIP C++14)

/**
 * 题目: 线粒体的“能量预算” (0/1 Knapsack)
 * 作者: Isaac Asimov (AI)
 * 算法: 动态规划 (DP) - 一维数组优化
 * 时间复杂度: O(N*C)
 */

#include <iostream>
#include <vector>
#include <algorithm> // max

using namespace std;

// 全局定义 DP 数组，防止栈溢出
// 大小开到 C 的最大值 + 余量
int dp[1005];

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int c, n;
    // 读入 ATP 总量 C 和 任务数 N
    cin >> c >> n;

    // dp 数组初始化
    // dp[0...c] 默认为 0 (全局变量已自动初始化，若在局部需 memset)
    
    // 循环处理每一个物品 (任务)
    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;

        // 0/1 背包的核心：倒序遍历容量
        // 范围：从最大容量 C 到当前物品重量 w
        for (int j = c; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

    // 最终答案是当容量为 C 时的最大价值
    cout << dp[c] << endl;

    return 0;
}

阿西莫夫的点评

1. 生物学意义： “权衡（Trade-off）”是进化论的核心。没有一种生物能拥有无限的资源，也没有一种策略是完美的。背包问题正是用数学语言量化了这种权衡。
2. 一维优化： 告诉学生，我们之所以能把二维 DP 压成一维，是因为细胞的能量是“流动的”。我们在做决策的那一瞬间，只需要知道“剩下的能量还能干什么”，而不需要关心“之前的能量具体是怎么花的”。这就是动态规划的无后效性。