Skip to content

1155: 0-1 Knapsack

题目

题目描述

你有一个可承受的最大重量为$m$的背包,和$n$个物品。 需要你选择其中一些物品放入背包,使得在不超过重量限制的前提下这些物品的价值尽量大。请注意控制使用内存。

输入格式

第一行是两个整数$n, m$, 分别表示物品的数量和背包的大小。
接下来$n$行,每行有两个整数。
第i+1行的两个整数$w_i, v_i$,分别表示第$i$个的物品的重量和价值。

输出格式

请输出背包最多可以装多大价值的物品。

样例输入

text 3 5 2 3 3 2 4 1

样例输出

text 5

数据范围

对于30\%的数据,$n \le 30, m \le 10^4$。
对于100\%的数据,$n \le 300, m \le 10^5, 0 \le w[i] \le 10^3, 0 \le v[i] \leq 10^6$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!