#CW69. 背包(satchel)

背包(satchel)

题目描述

有 nn 件物品和容量为 WW 的背包。物品 ii 的重量为 wiw_i,价值为 viv_i。你可以选择任意物品放入背包,但所选物品的重量和不能超过 WW。请最大化所选物品的价值和。除第一件物品外,每件物品都满足 w1≤wi≤w1+3w_1\le w_i\le w_1+3;这条限制是本题可以在大容量下求解的关键。每件物品最多选择一次,不能拆分,也不能重复使用。

输入格式

从 satchel.in 文件中读入。

第一行两个整数 n,Wn,W。接下来 nn 行,每行两个整数 wi,viw_i,v_i,依次表示第 ii 件物品的重量和价值。所有输入数值均为整数。

输出格式

向 satchel.out 文件中输出。

输出一个整数,表示满足重量限制时可以取得的最大价值。若所有物品都放不下,答案为 00。

样例 1 输入

4 6
2 1
3 4
4 10
3 4

样例 1 输出

11

样例 1 解释

取第 2,32,3 件(重量 3+4=7>63+4=7>6 放不下);最优是取第 2,42,4 件(重量 3+3=63+3=6,价值 4+4=84+4=8)或第 1,31,3 件(重量 2+4=62+4=6,价值 1+10=111+10=11),最大值为 1111。

样例 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≤n≤1001\le n\le 100,1≤W≤1091\le W\le 10^9,1≤wi≤1091\le w_i\le 10^9,1≤vi≤1071\le v_i\le 10^7,并且对 i=2,3,…,ni=2,3,\dots,n 有 w1≤wi≤w1+3w_1\le w_i\le w_1+3。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼51\sim 5 n≤16n\le 16
2 20 6∼106\sim 10 所有物品重量相等
3 30 11∼1511\sim 15 W≤100000W\le 100000
4 40 16∼2016\sim 20 完整约束