第 032 场 AtCoder Beginner Contest
翻译中…
Problem Statement
翻译中…
0/1ナップサック問題を解いてください。0/1ナップサック問題とは以下のような問題のことです。
翻译中…
$N$個の荷物があり、$i (1≦i≦N)$番目の荷物には価値$v_i$と重さ$w_i$が割り当てられている。- 許容重量
$W$のナップサックが1つある。 - 重さの和が
$W$以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。
翻译中…
Input
翻译中…
入力は以下の形式で標準入力から与えられる。
翻译中…
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$点が与えられる。
翻译中…
Output
翻译中…
出力は以下の形式で標準出力に行うこと。
翻译中…
$1$ 行目に、達成できる最大の合計価値を出力せよ。末尾の改行を忘れないこと。
翻译中…
样例
Input #1
3 10
15 9
10 6
6 4
Output #1
16
$2$ 番目と $3$ 番目のアイテムを選ぶと、合計の重みが $10$ で価値が $16$ となり、最大価値を達成できます。 この入出力例は、データセット $1,2,3$ の制約を満たしているため、全てのデータセットの採点に用いられます。
Input #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
Output #2
3673016420
この入出力例は、データセット $1$ の制約のみ満たしているため、データセット $2,3$ の採点には用いられません。
Input #3
10 2921
981421680 325
515936168 845
17309336 371
788067075 112
104855562 96
494541604 960
32007355 161
772339969 581
55112800 248
98577050 22
Output #3
3657162058
この入出力例は、データセット $3$ の制約を満たしていないため、データセット $3$ の採点には用いられません。
Input #4
10 936447862
854 810169801
691 957981784
294 687140254
333 932608409
832 42367415
642 727293784
139 870916042
101 685539955
853 243593312
369 977358410
Output #4
1686
この入出力例は、データセット $2$ の制約を満たしていないため、データセット $2$ の採点には用いられません。
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。