No.626 Randomized 01 Knapsack

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 25
作問者 : はむこはむこ
4 ProblemId : 2046 / 出題時の順位表

問題文

$n$個の荷物には、ランダムな価値$v_i$と重さ$w_i$が割り当てられています。
重さの和がW以下となるように荷物の集合をナップサックに入れた時の、ナップザックに入っている荷物の価値の和の最大値を求めてください。

運営より。
現在ジェネレーターでの乱数生成で落ちるケースを見つけていますが、キリがなさそうであればご連絡ください。

入力

n w
v_1 w_1
...
v_n w_n

$2\le n \le 5000$、整数。
$v_i, w_i$は$[1, 10^{12}]$の一様乱数で生成された整数。
$1 \le W \le n 10^{12}$、一様乱数で生成された整数。

出力

最後に改行してください。

サンプル

サンプル1
入力
3 10
15 9
10 6
6 4
出力
16

この入力は、$v_i, w_i$は$[1, 10^{12}]$の一様乱数で生成された整数ではないため、テストケースには含まれません。
$2, 3$番目を選んで、重さ$10$で価値$16$を得るのが最適です。

サンプル2
入力
100 514143443
948546988 109247822
64695760 71092171
1297072803 365949557
1491614786 4058510
837891549 779148613
1986354540 1363344517
1712407300 2113151085
80037390 1103335220
174015138 1112297200
1150886747 1226648052
237509729 682764599
1549905322 1437895315
26540299 375286638
438746167 758180494
1439547030 2022680400
1272323936 240610369
2131928221 1337019696
311702539 1281517376
1702969252 1803317325
1285575885 393377153
434982289 1124446776
1756721669 2147389588
1090114212 1836759058
1103241160 1264129350
801572609 106644258
343293753 1039082337
789408856 1893199074
329494003 815949154
121002063 768240169
1574129647 1560549092
643436920 698969935
1801159460 627881492
2035989630 2112861999
1909398867 1591475233
1768695675 1047491103
1984852385 56194315
24454231 1594090405
56100254 1114568442
1283365814 1159341413
231214143 2084938422
1265985670 574507895
976537110 2055394525
320223320 1306031112
723860030 441225382
2074271280 150506029
2001774473 570224551
849475963 1655450285
1198106043 737981944
1620828635 960021261
181973528 1242040661
2007512364 19342265
1298234975 2031966594
1613432669 1354335228
999051387 749314835
366192993 1230265530
686769608 1632178662
1804773424 1663306718
1540089539 2124996744
821854181 116465920
418738477 748641813
266971948 273029302
1318866363 1116447910
1928479586 369488757
1854429853 1401824572
1329510018 2036403381
496381584 1189538733
2055745645 1794616558
1074021678 1521694665
1001468137 2073073064
123525851 1367661129
1155854945 810295459
852356143 813144721
326118528 244962033
790657816 1147972708
361427952 1209396292
1896614520 628399900
1482425593 1067997235
1744847809 1263421530
1437485991 1451794014
517762453 619512360
1340713746 1014144036
1809051092 1248975742
661276945 735589121
623186758 1662745082
661178537 746712609
882922562 1817033481
1557008067 1735278704
482694553 1883126594
1980240736 1273352368
883615653 194185040
335265012 632746525
822584939 1817690604
1700743759 419949099
933628486 990746101
1871743112 1451390938
1610258461 1064973209
318051326 1271825904
166465302 979328270
2007415025 789652060
494589703 521109913
出力
9328651984

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。