第34~38题题目

（分数背包）小S有n块蛋糕，编号从1到n。第i块蛋糕的价值是wi，体积是vi。他有一个大

小为B的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过B。

他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个α

(0<α<1)，并将一块价值是w，体积为v的蛋糕切割成两块，其中一块的价值是α · w，体积

是α · v，另一块的价值是(1- a)·w，体积是(1-a)·v。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如n=3，B=8，三块蛋糕的价值分别是4、4、2，体积分别是5、3、2。那么最优的方案

就是将体积为5的蛋糕切成两份，一份体积是3，价值是2.4，另一份体积是2，价值是1.6，

然后把体积是3的那部分和后两块蛋糕打包进盒子。最优的价值之和是8.4，故程序输出

42/5。

输入的数据范围为：1≤n≤1000，1≤B≤105；1≤wi,vi≤100。提示：将所有的蛋糕按照性

价比wi/vi从大到小排序后进行贪心选择。试补全程序。

①处应填（）