問題文
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 。 数据集不满足