第 34 - 38 题 组合题

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

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

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

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块

价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是

（l-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≤10^5;1≤wi,vi≤100。

提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。

试补全程序。

①处应填()

第 39 - 43 题 组合题

（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分

值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其

子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于

空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。

提示：考虑优化朴素的动态规划算法，将前 位和后 位分开计算。

Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。

试补全程序。

①处应填（）