NP Knapsack

NP Knapsack

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

我们已经学过了基于动态规划的0-1背包算法,即用状态\(f[x][u]\)表示用前\(x\)件物品填充容量限制为\(u\)的子背包,最多可以产生多少价值。但动态规划算法只局限于\(u\)的范围较小,且均为非负整数的情形。显然当\(u\)为浮点数时,这种动态规划解法就不再适用了。
本题就是每件物品重量、价值均为浮点数的0-1背包问题。

输入格式

输入第一行是一个正整数\(T\),表示测试数据组数。之后每组数据:
第一行是一个正整数\(N\),表示物品的件数;然后是一个浮点数\(W\),表示背包的总容量;
之后\(N\)行,每行两个浮点数\(w_i, v_i\),分别表示该件物品的重量与价值。
所有浮点数均保留至多3位小数。

输出格式

每组数据输出一行,在选取物品的总重量不超过\(W\)的前提下,总价值最多可以是多少,四舍五入保留3位小数。

样例

输入

2
3 10.0
3.5 1.75
4.0 3.2
6.4 3.25
4 10.0
3.5 150.01
2.5 80.02
6.1 450.04
4.1 320.08

输出

5.000
600.050

数据规模及约定

\(T \le 10, \quad N \le 20, \quad 0.0 < W < 10^5, \quad 0.0 < w_i < W, \quad 0.0 < v_i < 10^5\)
为了避免浮点数精度误差带来的影响,保证对于所有物品的任意一个子集,\(\lvert \sum w_i - W \rvert > 10^{-3}\)
数据已大幅加强
时间限制1s,空间限制64MB。

2019.2.1测验

未参加
状态
已结束
规则
OI
题目
3
开始于
2019-02-01 14:00
结束于
2019-02-01 17:30
持续时间
3.5 小时
主持人
参赛人数
30