你好！我是你的OI金牌教练。

到目前为止，我们已经复习了图论、树形结构、二分答案、双指针、差分、前缀和、单调栈。 今天，我们补上算法竞赛中最核心、最千变万化的一块拼图——动态规划 (Dynamic Programming, DP)。

我们将结合明朝**“郑和下西洋”**的壮阔历史，来讲解 DP 中的入门必修课——0/1 背包问题。

---

第一部分：背景知识讲解

1. 郑和下西洋 (Zheng He's Voyages)

明朝永乐年间（1405年起），为了宣扬国威、加强与海外各国的联系，明成祖朱棣派遣郑和率领庞大的舰队七次出使西洋（今东南亚、印度洋沿岸一带）。

• 宝船：郑和的舰队中，最大的船被称为“宝船”，长四十四丈，宽十八丈，是当时世界上最大的木帆船。
• 朝贡贸易：舰队所到之处，各国纷纷向明朝进贡珍宝（如象牙、香料、宝石、长颈鹿/麒麟等），以示友好。

2. 装载难题

虽然宝船巨大，但载重量依然是有限的。 在返航时，面对各国进贡的琳琅满目的宝物，郑和需要做出取舍：

• 每件宝物都有一定的重量。
• 每件宝物都有一定的文化价值（或皇帝的喜爱程度）。
• 目标：在不超载的前提下，装载总价值最高的宝物回京。

3. 算法模型：0/1 背包问题

为什么叫“0/1”？因为对于每一件宝物，我们只有两种选择：

• 0：不拿（扔掉）。
• 1：拿走（装船）。 不能切开拿一半，也不能拿多次（每件宝物是唯一的）。 这类问题不能用“贪心法”（比如只拿最贵的，或者只拿性价比最高的），必须用动态规划来寻找全局最优解。

---

第二部分：题目内容

题目名称：宝船的装载 (Loading the Treasure Ship)

题目描述

郑和的船队即将结束在古里国（今印度）的贸易，准备返航。当地国王进贡了 $N$ 件珍稀宝物。 经过鉴定，第 $i$ 件宝物的重量为 $W_i$，其对应的文化价值为 $V_i$。

郑和的主宝船目前的剩余载重量为 $M$。 请你制定一个装载方案，从这 $N$ 件宝物中选出若干件装上船，使得：

1. 被选宝物的总重量不超过 $M$。
2. 被选宝物的总文化价值最大。

请输出这个最大的总价值。

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示宝物的数量。
• $M$ 表示宝船的剩余载重量。

接下来 $N$ 行，每行包含两个正整数 $W_i, V_i$。

• $W_i$ 表示第 $i$ 件宝物的重量。
• $V_i$ 表示第 $i$ 件宝物的价值。

输出格式

输出一行一个整数，表示在不超过载重限制的情况下，能获得的最大总价值。

输入输出样例 #1

输入：

4 10
2 6
5 3
4 5
2 4

输出：

15

样例 #1 解释： 共有 4 件宝物，载重限制 10。

• 物品1: 重2, 值6
• 物品2: 重5, 值3
• 物品3: 重4, 值5
• 物品4: 重2, 值4

方案推演：

• 如果贪心选价值最高的（物品1），剩载重8。再选物品3（值5，重4），剩4。再选物品4（值4，重2），剩2。总重 2+4+2=8 <= 10，总值 6+5+4 = 15。
• 还有更好的吗？
  • 选物品 1, 3, 4 $\to$ 重量 $2+4+2=8 \le 10$，价值 $6+5+4=15$。
  • 选物品 1, 2, 4 $\to$ 重量 $2+5+2=9 \le 10$，价值 $6+3+4=13$。
• 最优解确实是 15。

输入输出样例 #2

输入：

5 20
10 10
10 10
10 10
12 25
8 10

输出：

35

样例 #2 解释：

• 物品：A(10,10), B(10,10), C(10,10), D(12,25), E(8,10)。容量 20。
• 只有容量 20，装不了三个 10 重量的。
• 方案 1：装 A, B。总重 20，总值 20。
• 方案 2：装 D, E。总重 12+8=20，总值 25+10=35。
• 显然后者更优，输出 35。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 100$ (物品数量)
• $1 \le M \le 1000$ (载重量)
• $1 \le W_i, V_i \le 1000$
• 注：这是最基础的范围，实际上 0/1 背包的一维优化写法可以处理 $N=5000, M=5000$ 的级别。

---