D - ナップサック問題
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 512 MB
問題文
0/1ナップサック問題を解いてください。0/1ナップサック問題とは以下のような問題のことです。
- N 個の荷物があり、i (1≦i≦N) 番目の荷物には価値 v_i と重さ w_i が割り当てられている。
- 許容重量 W のナップサックが1つある。
- 重さの和が 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 つの条件のうち少なくとも1つの条件が成り立つ。
部分点
この問題には部分点が設定されている。満点は 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 番目と 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 の採点には用いられません。