第38题
（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。
那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。
输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比 wi/vi 从大到小排序后进行贪心选择。
试补全程序。
- #include <cstdio>
- using namespace std;
- const int maxn = 1005;
- int n, B, w[maxn], v[maxn];
- int gcd(int u, int v) {
- if (v == 0)
- return u;
- return gcd(v, u % v);
- }
- void print(int w, int v) {
- int d = gcd(w, v);
- w = w / d;
- v = v / d;
- if (v == 1)
- printf("%d\n", w);
- else
- printf("%d/%d\n", w, v);
- }
- void swap(int &x, int &y) {
- int t = x; x = y; y = t;
- }
- int main() {
- scanf("%d %d", &n, &B);
- for (int i = 1; i <= n; i ++) {
- scanf("%d%d", &w[i], &v[i]);
- }
- for (int i = 1; i < n; i ++)
- for (int j = 1; j < n; j ++)
- if ( ① ) {
- swap(w[j], w[j + 1]);
- swap(v[j], v[j + 1]);
- }
- int curV, curW;
- if ( ② ) {
- ③
- } else {
- print(B * w[1], v[1]);
- return 0;
- }
- for (int i = 2; i <= n; i ++)
- if (curV + v[i] <= B) {
- curV += v[i];
- curW += w[i];
- } else {
- print( ④ );
- return 0;
- }
- print( ⑤ );
- return 0;
- }
⑤处应填（ ）
