题库 信息学奥赛题库 题目列表 (分数背包)小 S 有 n 块蛋糕,...
组合题

(分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。 他打算选择一些蛋糕装入盒子,他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大,他可以任意切割蛋糕。具体来说,他可以选择一个a (0<a<l),并将一块价值是 w,体积为 v 的蛋糕切割成两 块,其中一块的价值是 a·w,体积是 a·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≤10^5,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;
}
第1题 单选

处应填( )

A.

 w[j] / v[j] < w[j + 1] / v [j +1]

B.

w[j] / v[j] > w[j + 1] / v [j +1]

C.

 v[j] * w[j + 1] < v[j + 1] * w[j]

D.

 w[j] * v[j + 1] < w[j + 1] * v[j]

第2题 单选

处应填( )

A.

w[1] <= B

B.

v[1] <= B

C.

w[1] >= B

D.

v[1] >= B

第3题 单选

处应填( )

A.

print(v[1],w[1]); return 0;

B.

curV = 0; curW = 0;

C.

print(w[1], v[1]); return 0;

D.

curV = v[1]; curW = w[1];

第4题 单选

处应填()

A.

curW * v[i] + curV * w[i], v[i]

B.

(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]

C.

curW + v[i], w[i]

D.

curW * v[i] + (B - curV) * w[i], v[i]

第5题 单选

处应填( )

A.

curW,curV

B.

curW, 1

C.

curV, curW

D.

curV, 1

题目信息
完善程序 初赛 2020年
-
正确率
0
评论
178
点击