84440 - 又见完全背包

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

有 $n$ 种物品，第 $i$ 种物品的重量和价格为 $w_i、v_i$ 。每种物品数量无限。背包最大载重量为 $C$ 。今要把背包装满，并使得背包内物品价值之和最大。

第一行两个正整数 $n$ 和 $C$ 。

第二行为 $n$ 个正整数 $w_i, i=1,2,...,n$ 。

第三行为 $n$ 个正整数 $v_i, i=1,2,...,n$ 。

背包所能容纳物品的最大价值。

4 10
2 3 4 7
1 3 5 9

对于100%的数据，有 $1≤N≤100，1≤C≤10^{12},C/100≤w_i≤10^{12}，1≤v_i≤1000。$

原创