🎒 0/1 背包问题 —— 太郎的物品选择

📖 题目描述

太郎有 N 件物品，每件物品都有：

• 重量：w[i]
• 价值：v[i]

他有一个容量为 W 的背包，太郎希望从这些物品中选出若干件装入背包中，使得：

选中的物品总重量 ≤ W，并且价值总和最大。

📌 输入格式

输入从标准输入读取，格式如下：

N W
w₁ v₁
w₂ v₂
...
wₙ vₙ

• N：物品数量 (\(1 \le N \le 100\))
• W：背包容量 (\(1 \le W \le 10^5\))
• w[i]：第 i 件物品的重量 (\(1 \le w[i] \le W\))
• v[i]：第 i 件物品的价值 (\(1 \le v[i] \le 10^9\))

📤 输出格式

输出一个整数，表示太郎能带回家的最大总价值。

📘 输入输出样例

样例 1

输入：
3 8
3 30
4 50
5 60

输出：
90

解释：
选择物品 1 和 3，重量之和 3 + 5 = 8，价值 30 + 60 = 90。

样例 2

输入：
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

输出：
5000000000

提示：
答案可能超过 32 位整数范围（注意使用 long long 类型）。

样例 3

输入：
6 15
6 5
5 6
6 4
6 6
3 5
7 2

输出：
17

解释：
选择物品 2、4、5，重量和为 5 + 6 + 3 = 14，价值和为 6 + 6 + 5 = 17。