问题描述
小鱼儿在一次探险途中发现了一个山洞，并且在这个山洞里找到了宝藏，可是小鱼儿发现想要把宝藏全部带走是不可能的（因为他只带了一个袋子），不过很快他就发现每个宝物旁边都有几个字，上面写着宝物的体积和价值，而且这些宝物可以分割成任意大小。小鱼儿想知道如何选取宝物，才能使带走宝物的价值最大。
预置代码
输入
第一行有两个整数v和n,表示袋子的容量和宝物的数量。（0<n<=100,010000)
接下来n行每行两个整数，分别表示宝物的体积和价值。
输出
在单独的一行中输出一个数，表示能够带走宝物的最大价值，结果保留两位小数。
输入样列
10 3
10 30
11 55
4 30
输出样例
60.00
#include
int main() {
int v, n, k = 0;
int a[99], b[99];
double r[99]={0}, he = 0, jiazhi = 0, p;
scanf("%d %d", &v, &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &a[i], &b[i]);
r[i] = b[i] / 1.0 / a[i];
}
for (int i = 0; i < n - 1; i++) {
for (int j = i+1; j < n ; j++) {
if (r[i] 0;i= v) {
he = he - a[i];
break;
}
k++;
jiazhi += b[i];
}
p = r[k];
printf("%.2lf", jiazhi + (v - he) * p);
return 0;
}
我自己在网上搜集过样例，进入运行都是正确的，但是学习系统认为我答案有误，恳求指正。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int v, c;
double rate;
} node[110];
bool cmp(Node a, Node b) {
return a.rate > b.rate;
}
int main() {
int n, v;
scanf("%d %d", &v, &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &node[i].v, &node[i].c);
node[i].rate = (double)node[i].c / node[i].v;
}
sort(node, node + n, cmp);
int remain = v;
double value = 0;
for (int i = 0; i < n; i++) {
if (remain >= node[i].v) {
value += node[i].c;
remain -= node[i].v;
} else {
value += node[i].rate * remain;
break;
}
}
printf("%.2lf\n", value);
return 0;
}