题目分析与思路提示

1. 为什么不能用贪心？

比如：容量 10。 物品 A：重 10，值 20 （性价比 2.0） 物品 B：重 5，值 15 （性价比 3.0） 物品 C：重 5，值 15 （性价比 3.0）

• 按性价比贪心：选 B，剩容量 5。再选 C，剩容量 0。总值 30。
• 选 A：总值 20。
• 这里贪心是对的？不一定。 再看：容量 50。 A: 50, 100 (性价比 2) B: 26, 60 (性价比 2.3) C: 26, 60 (性价比 2.3)
• 贪心选 B，剩 24，装不下 C 了。总值 60。
• 实际上选 A，总值 100。 结论：贪心是不靠谱的，因为物品不可拆分，留下的空隙可能造成浪费。

2. 动态规划思路 (DP)

我们定义状态 $dp[j]$ 为：当载重量限制为 $j$ 时，能装下的最大价值。

状态转移方程： 面对第 $i$ 件物品（重量 $w$，价值 $v$），对于每一个可能的载重量 $j$（$j$ 从 $M$ 到 0），我们有两个选择：

1. 不装它：价值还是原来的 $dp[j]$（即前 $i-1$ 件物品在载重 $j$ 下的最大值）。
2. 装它：前提是 $j \ge w$。如果装它，那么我们就要腾出 $w$ 的空间，去找“载重 $j-w$ 时的最大价值”，然后加上 $v$。即 $dp[j-w] + v$。

我们取两者中的最大值：

3. 空间优化（滚动数组）

原本的状态应该是二维的 $dp[i][j]$（前 $i$ 个物品，载重 $j$）。但我们发现第 $i$ 行的状态只和第 $i-1$ 行有关。 所以我们可以压缩成一维数组 $dp[j]$。 关键点：为了保证在计算 $dp[j]$ 时，用到的 $dp[j-w]$ 是“上一轮（第 $i-1$ 个物品）”的状态，而不是“这一轮（第 $i$ 个物品）已经更新过”的状态，内层循环必须从大到小 (倒序) 遍历。

算法流程：

1. 初始化 dp 数组全为 0。
2. 外层循环遍历每个物品 $i$ 从 1 到 $N$。
   • 读取 $W_i, V_i$。
   • 内层循环遍历载重 $j$ 从 $M$ 到 $W_i$ (倒序!)。
     • dp[j] = max(dp[j], dp[j - W_i] + V_i);
3. 输出 dp[M]。

4. 复杂度分析

• 时间复杂度：$O(N \times M)$。双重循环。
• 空间复杂度：$O(M)$。只需一个一维数组。

参考代码 (C++14)

/**
 * 题目：宝船的装载 (Loading the Treasure Ship)
 * 难度：GESP 6级
 * 算法：动态规划 (0/1 Knapsack Problem)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

// 定义最大载重，根据题目范围 M <= 1000
// 如果题目范围变大，这里要相应调大
const int MAX_M = 5005; 
int dp[MAX_M]; 

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // dp[j] 表示容量为 j 时的最大价值
    // 初始化为 0，因为一件不装价值为 0
    for (int j = 0; j <= M; ++j) dp[j] = 0;

    // 逐个处理物品
    for (int i = 1; i <= N; ++i) {
        int w, v;
        cin >> w >> v;

        // 0/1 背包的核心：倒序遍历容量
        // 范围从 M 到 w (因为如果容量小于 w，根本装不下这个物品，dp值不变)
        for (int j = M; j >= w; --j) {
            // 状态转移方程：
            // 不装：dp[j] (保持原样)
            // 装：  dp[j - w] + v
            // 取最大值
            if (dp[j - w] + v > dp[j]) {
                dp[j] = dp[j - w] + v;
            }
        }
    }

    cout << dp[M] << endl;

    return 0;
}

数据生成器 (Data Generator)

用于生成 1.in ~ 10.in 及其标准答案。覆盖了小数据、大数据、必须贪心失效的数据等。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
int solve(int N, int M, const vector<pair<int, int>>& items) {
    vector<int> dp(M + 1, 0);
    for (const auto& item : items) {
        int w = item.first;
        int v = item.second;
        for (int j = M; j >= w; --j) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    return dp[M];
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<pair<int, int>> items;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 4; M = 10;
            items = {{2,6}, {5,3}, {4,5}, {2,4}};
        }
        else if (i == 2) {
            // 样例2
            N = 5; M = 20;
            items = {{10,10}, {10,10}, {10,10}, {12,25}, {8,10}};
        }
        else if (i == 3) {
            // 小规模随机
            N = 10; M = 50;
            for(int k=0; k<N; k++) items.push_back({randRange(1, 20), randRange(1, 100)});
        }
        else if (i == 4) {
            // 贪心失效数据：轻物体性价比低，重物体性价比高但难塞
            N = 5; M = 100;
            items = {{100, 200}, {51, 100}, {51, 100}, {51, 100}, {51, 100}};
            // 贪心看性价比：100/100=2, 100/51 < 2。会想拿第一个。
            // 实际只能拿一个。但如果拿两个51的，总重102超了。
            // 这里设计有点问题，重写：
            // A: 20kg, $40 (ratio 2)
            // B: 15kg, $25 (ratio 1.6)
            // C: 15kg, $25 (ratio 1.6)
            // Cap 30. 贪心拿A剩10，总40。 DP拿B+C，总50。
            items = {{20, 40}, {15, 25}, {15, 25}};
            M = 30; N = 3;
        }
        else if (i == 5) {
            // 全都能装下
            N = 50; M = 5000;
            for(int k=0; k<N; k++) items.push_back({randRange(1, 10), randRange(1, 10)});
        }
        else if (i == 6) {
            // 只能装很少（重量都很大）
            N = 50; M = 100;
            for(int k=0; k<N; k++) items.push_back({randRange(80, 120), randRange(100, 200)});
        }
        else {
            // 大规模测试 (N=100, M=1000) -> 扩展到题目上限附近
            N = 100; 
            if (i >= 9) M = 1000; else M = 500;
            
            for(int k=0; k<N; k++) {
                items.push_back({randRange(1, M/5), randRange(1, 1000)});
            }
        }

        // 写入输入
        fin << N << " " << M << endl;
        for (const auto& item : items) {
            fin << item.first << " " << item.second << endl;
        }

        // 写入输出
        fout << solve(N, M, items) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}