No.626 Randomized 01 Knapsack
はむこ問題文最終更新日: 2018-01-08 22:38:30
問題文
$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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。