yukicoder-626
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
display: block;
padding: 9.5px;
margin: 0 0 10px;
font-size: 13px;
line-height: 1.42857143;
color: #333;
word-break: break-all;
word-wrap: break-word;
background-color: #f5f5f5;
border: 1px solid #ccc;
border-radius: 4px;
}
</style>
}}}
== [https://yukicoder.me/problems/no/626 No.626 Randomized 01 Knapsack] ==
=== Description ===
{{{
#!html
<p>给出 $n$ 个物品的价值 $v_i$ 和重量 $w_i$，以及背包容量 $w$，求 01 背包问题的最大价值。</p>
}}}
=== Input ===
{{{
#!html
<p class="input">
$n$ $w$<br/>
$v_1$ $w_1$<br/>
$\vdots$<br/>
$v_n$ $w_n$
</p>
<p>$2 \le n \le 5000$，$v_i$ 与 $w_i$ 均为 $[1, 10^{12}]$ 内的随机整数，$1 \le w \le n \times 10^{12}$，也是随机整数。</p>
}}}
=== Output ===
{{{
#!html
<p>输出 01 背包问题的最大价值。</p>
}}}
=== Sample ===
==== Sample 1 ====
输入
{{{
#!html
<pre>
3 10
15 9
10 6
6 4
</pre>
}}}
输出
{{{
#!html
<pre>
16
</pre>
<p>这个数据只是样例，最后的测试数据会是 $[1, 10^{12}]$ 范围内的随机整数。</p>
}}}
==== Sample 2 ====
输入
{{{
#!html
<pre>
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
</pre>
}}}
输出
{{{
#!html
<pre>
9328651984
</pre>
}}}No.626 Randomized 01 Knapsack
Description
给出 $n$ 个物品的价值 $v_i$ 和重量 $w_i$，以及背包容量 $w$，求 01 背包问题的最大价值。
Input
$n$ $w$
$v_1$ $w_1$
$\vdots$
$v_n$ $w_n$
$2 \le n \le 5000$，$v_i$ 与 $w_i$ 均为 $[1, 10^{12}]$ 内的随机整数，$1 \le w \le n \times 10^{12}$，也是随机整数。
Output
输出 01 背包问题的最大价值。
Sample
Sample 1
输入
3 1015 910 66 4
输出
16
这个数据只是样例，最后的测试数据会是 $[1, 10^{12}]$ 范围内的随机整数。
Sample 2
输入
100 514143443948546988 10924782264695760 710921711297072803 3659495571491614786 4058510837891549 7791486131986354540 13633445171712407300 211315108580037390 1103335220174015138 11122972001150886747 1226648052237509729 6827645991549905322 143789531526540299 375286638438746167 7581804941439547030 20226804001272323936 2406103692131928221 1337019696311702539 12815173761702969252 18033173251285575885 393377153434982289 11244467761756721669 21473895881090114212 18367590581103241160 1264129350801572609 106644258343293753 1039082337789408856 1893199074329494003 815949154121002063 7682401691574129647 1560549092643436920 6989699351801159460 6278814922035989630 21128619991909398867 15914752331768695675 10474911031984852385 5619431524454231 159409040556100254 11145684421283365814 1159341413231214143 20849384221265985670 574507895976537110 2055394525320223320 1306031112723860030 4412253822074271280 1505060292001774473 570224551849475963 16554502851198106043 7379819441620828635 960021261181973528 12420406612007512364 193422651298234975 20319665941613432669 1354335228999051387 749314835366192993 1230265530686769608 16321786621804773424 16633067181540089539 2124996744821854181 116465920418738477 748641813266971948 2730293021318866363 11164479101928479586 3694887571854429853 14018245721329510018 2036403381496381584 11895387332055745645 17946165581074021678 15216946651001468137 2073073064123525851 13676611291155854945 810295459852356143 813144721326118528 244962033790657816 1147972708361427952 12093962921896614520 6283999001482425593 10679972351744847809 12634215301437485991 1451794014517762453 6195123601340713746 10141440361809051092 1248975742661276945 735589121623186758 1662745082661178537 746712609882922562 18170334811557008067 1735278704482694553 18831265941980240736 1273352368883615653 194185040335265012 632746525822584939 18176906041700743759 419949099933628486 9907461011871743112 14513909381610258461 1064973209318051326 1271825904166465302 9793282702007415025 789652060494589703 521109913
输出
9328651984