#CW69. 背包(satchel)
背包(satchel)
题目描述
有 件物品和容量为 的背包。物品 的重量为 ,价值为 。你可以选择任意物品放入背包,但所选物品的重量和不能超过 。请最大化所选物品的价值和。除第一件物品外,每件物品都满足 ;这条限制是本题可以在大容量下求解的关键。每件物品最多选择一次,不能拆分,也不能重复使用。
输入格式
从 satchel.in 文件中读入。
第一行两个整数 。接下来 行,每行两个整数 ,依次表示第 件物品的重量和价值。所有输入数值均为整数。
输出格式
向 satchel.out 文件中输出。
输出一个整数,表示满足重量限制时可以取得的最大价值。若所有物品都放不下,答案为 。
样例 1 输入
4 6
2 1
3 4
4 10
3 4
样例 1 输出
11
样例 1 解释
取第 件(重量 放不下);最优是取第 件(重量 ,价值 )或第 件(重量 ,价值 ),最大值为 。
样例 2 输入
4 6
2 1
3 7
4 10
3 6
样例 2 输出
13
样例 3 输入
4 10
1 100
1 100
1 100
1 100
样例 3 输出
400
样例 4 输入
4 1
10 100
10 100
10 100
10 100
样例 4 输出
0
数据范围
,,,,并且对 有 。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 10 | ||
| 2 | 20 | 所有物品重量相等 | |
| 3 | 30 | ||
| 4 | 40 | 完整约束 |