NP Knapsack
题目描述
我们已经学过了基于动态规划的0-1背包算法,即用状态表示用前件物品填充容量限制为的子背包,最多可以产生多少价值。但动态规划算法只局限于的范围较小,且均为非负整数的情形。显然当为浮点数时,这种动态规划解法就不再适用了。
本题就是每件物品重量、价值均为浮点数的0-1背包问题。
输入格式
输入第一行是一个正整数,表示测试数据组数。之后每组数据:
第一行是一个正整数,表示物品的件数;然后是一个浮点数,表示背包的总容量;
之后行,每行两个浮点数,分别表示该件物品的重量与价值。
所有浮点数均保留至多3位小数。
输出格式
每组数据输出一行,在选取物品的总重量不超过的前提下,总价值最多可以是多少,四舍五入保留3位小数。
样例
输入
输出
数据规模及约定
为了避免浮点数精度误差带来的影响,保证对于所有物品的任意一个子集,
数据已大幅加强
时间限制1s,空间限制64MB。