简答题
偏难
#7093
圣诞老人的礼物 圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的…
圣诞老人的礼物
圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果,请问圣诞老人最多能带走多大价值的糖果。
时间限制:1000
内存限制:65536
输入
第一行由两个部分组成,分别为糖果箱数正整数n(1 = n = 100),驯鹿能承受的最大重量正整数w(0<w<10000),两个数用空格隔开。其余n行每行对应一箱糖果,由两部分组成,分别为一箱糖果的价值正整数v和重量正整数w,中间用空格隔开。
输出
输出圣诞老人能带走的糖果的最大总价值,保留1位小数。输出为一行,以换行符结束。
样例输入
4 15 100 4 412 8 266 7 591 2
样例输出
1193.0
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct gift {
int value;
int weight;
double density;
} gf[101];
bool cmp(gift f1, gift f2) { // 按照单重价值从大到小排序
return f1.density > f2.density;
}
int main() {
int n, w;
cin >> n >> w;
for (int i = 0; i < n; i++) {
cin >> gf[i].value >> gf[i].weight;
gf[i].density = 1.0 * gf[i].value / gf[i].weight;
}
sort(gf, gf + n, cmp);
double totw = 0, totv = 0; // 注意到w为int型,可拆分为double型
// 所以新建一个double型保存背包剩余重量
for (int i = 0; i < n; i++) {
if (totw + gf[i].weight <= w) {
totw += gf[i].weight;
totv += gf[i].value;
} else {
totv += gf[i].density * (w - totw);
totw = w;
break;
}
}
printf("%.1lf", totv);
return 0;
}</pre>
这道题暂未补解析。