← 返回题目列表

AtCoder · abc032_d

D. 背包问题

中文机器翻译题面 查看原题

問題文

0/1 请解决背包问题。 0/1背包问题是如下问题。 我有

  • N 件行李。i (1≦i≦N) 第一个包裹有价值 v_i 和重量 已分配 w_i 。 有一个
  • 許容重量 W 背包。
  • 权重之和为 W 选择下列一组行李并将其装入背包时,求数值总和的最大值。但同一行李只能选择一次。

入力

输入将以以下格式从标准输入提供。

N W
v_1 w_1
v_2 w_2
:
v_N w_N
  • 1 行包含一个表示包数的整数。 N (1≦N≦200) 和代表背包允许重量的整数 来自行 W(1≦W≦10^9) 用空格分隔。
  • 2 从线 N 行提供有关每个包的信息。这几天之一 一个整数,表示第 i(1≦i≦N) 第几行包含,i 个包的值 v_i (1≦v_i≦10^9) 和代表权重的整数 w_i (1≦w_i≦10^9) 用空格分隔。
  • 「N≦30”, “全部i(1≦i≦N) 关于 1≦w_i≦1000”, “全部i(1≦i≦N) 关于 1≦v_i≦1000” 3 这些条件至少有一个为真。

部分点

针对此问题设置了部分分数。满分是 100 点。

  • N≦30 的数据集 如果您正确回答 1 , 给出34 点。 如果您正确回答
  • N≦200 和所有 如果您正确回答 i(1≦i≦N) 关于 1≦w_i≦1000 的数据集 如果您正确回答 2 ,除了上述分数外,您还将获得额外的分数。 33 点。 如果您正确回答
  • N≦200 和所有 如果您正确回答 i(1≦i≦N) 关于 1≦v_i≦1000 的数据集 如果您正确回答 3 ,除了上述分数外,您还将获得额外的分数。 33 点。 如果您正确回答

出力

输出应按以下格式执行到标准输出。 在行

1 上,打印可以达到的最大总值。不要忘记最后的换行符。


入力例1

3 10
15 9
10 6
6 4

出力例1

16

2 th 和 如果您选择第 3 项,则总重量将为 该值为 10 值得 16 并达到最大值。 此输入/输出示例使用数据集 由于它满足 1,2,3 约束,因此用于对所有数据集进行评分。


入力例2

30 499887702
128990795 137274936
575374246 989051853
471048785 85168425
640066776 856699603
819841327 611065509
704171581 22345022
536108301 678298936
119980848 616908153
117241527 28801762
325850062 478675378
623319578 706900574
998395208 738510039
475707585 135746508
863910036 599020879
340559411 738084616
122579234 545330137
696368935 86797589
665665204 592749599
958833732 401229830
371084424 523386474
463433600 5310725
210508742 907821957
685281136 565237085
619500108 730556272
88215377 310581512
558193168 136966252
475268130 132739489
303022740 12425915
122379996 137199296
304092766 23505143

出力例2

3673016420

此输入/输出示例使用数据集 由于仅满足 1 约束,因此数据集 它不用于评分 2,3 。 数据集不满足


入力例3

10 2921
981421680 325
515936168 845
17309336 371
788067075 112
104855562 96
494541604 960
32007355 161
772339969 581
55112800 248
98577050 22

出力例3

3657162058

此输入/输出示例使用数据集 由于仅满足 3 约束。 3 。 数据集不满足


入力例4

10 936447862
854 810169801
691 957981784
294 687140254
333 932608409
832 42367415
642 727293784
139 870916042
101 685539955
853 243593312
369 977358410

出力例4

1686

此输入/输出示例使用数据集 由于仅满足 2 约束。 2 。 数据集不满足