1725: CSP-S20分数背包(完善程序)
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Special Judger
Creator:
Submit:6
Solved:0
Description
1.(分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 w(i),体积是 v(i)。他有一个大小为 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≤w(i),v(i)≤100。
提示:将所有的蛋糕按照性价比 w(i)/v(i) 可从大到小排序后进行贪心选择。
试补全程序。
#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
为了使盒子里的蛋糕价值之和更大,他可以任意切割蛋糕。具体来说,他可以选择一个 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≤w(i),v(i)≤100。
提示:将所有的蛋糕按照性价比 w(i)/v(i) 可从大到小排序后进行贪心选择。
试补全程序。
#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