完善程序（1） 1-5题 组合题 （分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。 他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。 为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0 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; }
正确答案：完善程序①答案：w[j]*v[j+1] < w[j+1]*v[j]（按性价比升序冒泡）。核心：性价比排序。
试卷来源：2020 CSP-S提高级（第一轮）C++真题