AT_abc032_d.[ABC032D] ナップサック問題

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

请解决 0/1 背包问题。0/1 背包问题的定义如下：

有 $N$ 个物品，第 $i\ (1\leq i\leq N)$ 个物品有价值 $v_i$ 和重量 $w_i$ 。
有一个最大承重为 $W$ 的背包。
请选择若干个物品放入背包，使得总重量不超过 $W$ ，并且总价值最大。每个物品最多只能选择一次。

输入格式

输入以如下格式从标准输入读入。

$N$ $W$
$v_1$ $w_1$
$v_2$ $w_2$
$\vdots$
$v_N$ $w_N$

第 $1$ 行包含两个整数，分别表示物品数量 $N\ (1\leq N\leq 200)$ 和背包的最大承重 $W\ (1\leq W\leq 10^9)$ ，以空格分隔。
接下来的 $N$ 行，每行包含两个整数，第 $i$ 行表示第 $i$ 个物品的价值 $v_i\ (1\leq v_i\leq 10^9)$ 和重量 $w_i\ (1\leq w_i\leq 10^9)$ ，以空格分隔。
下列三个条件中至少有一个成立：「 $N\leq 30$ 」、「所有 $i\ (1\leq i\leq N)$ 满足 $1\leq w_i\leq 1000$ 」、「所有 $i\ (1\leq i\leq N)$ 满足 $1\leq v_i\leq 1000$ 」。

输出格式

请输出一个整数，表示能够达到的最大总价值。输出后需换行。

输入输出样例

输入#1
```
3 10
15 9
10 6
6 4
```
输出#1
```
16
```

输入#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

输入#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

输入#4

10 936447862
854 810169801
691 957981784
294 687140254
333 932608409
832 42367415
642 727293784
139 870916042
101 685539955
853 243593312
369 977358410

输出#4

说明/提示

部分分

本题设有部分分，满分为 $100$ 分。

若正确解决满足 $N\leq 30$ 的数据集 1，可获得 $34$ 分。
若正确解决满足 $N\leq 200$ 且所有 $i\ (1\leq i\leq N)$ 满足 $1\leq w_i\leq 1000$ 的数据集 2，可额外获得 $33$ 分。
若正确解决满足 $N\leq 200$ 且所有 $i\ (1\leq i\leq N)$ 满足 $1\leq v_i\leq 1000$ 的数据集 3，可额外获得 $33$ 分。

样例解释 1

选择第 $2$ 个和第 $3$ 个物品，总重量为 $10$ ，总价值为 $16$ ，可以达到最大价值。该输入输出样例满足数据集 $1,2,3$ 的约束，因此用于所有数据集的评测。

样例解释 2

该输入输出样例仅满足数据集 $1$ 的约束，因此不用于数据集 $2,3$ 的评测。

样例解释 3

该输入输出样例不满足数据集 $3$ 的约束，因此不用于数据集 $3$ 的评测。

样例解释 4

该输入输出样例不满足数据集 $2$ 的约束，因此不用于数据集 $2$ 的评测。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页