金银岛

题目

某天KID利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,KID虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同,分别为n 1, n 2, … , n s,同时每个种类的金属总的价值也不同,分别为v 1,v 2, …, v s。KID想一次带走价值尽可能多的金属,问他最多能带走价值多少的金属。注意到金属是可以被任意分割的,并且金属的价值和其重量成正比。

Input
第1行是测试数据的组数k,后面跟着k组输入。

每组测试数据占3行,第1行是一个正整数w (1 <= w <= 10000),表示口袋承重上限。第2行是一个正整数s (1 <= s <=100),表示金属种类。第3行有2s个正整数,分别为n 1, v 1, n 2, v 2, … , n s, v s分别为第一种,第二种,…,第s种金属的总重量和总价值(1 <= n i <= 10000, 1 <= v i <= 10000)。
Output
k行,每行输出对应一个输入。输出应精确到小数点后2位。
Sample Input

1
2
3
4
5
6
7
2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

Sample Output

1
2
171.93
508.00

题解

该题跟圣诞老人题类似传送,单位重量内价值越高优先选择。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
const int MAXSIZE=10000+5;
using namespace std;
struct Node{
int weight;
int value;
double single;
};
bool cmp(struct Node a,struct Node b){return a.single>b.single;}
int main(){
int Case;
cin>>Case;
while(Case--){
int w;
cin>>w;
int s;
cin>>s;
struct Node arr[MAXSIZE];
for(int i=0;i<s;i++){
cin>>arr[i].weight>>arr[i].value;
arr[i].single=arr[i].value*1.0/arr[i].weight;
}
sort(arr,arr+s,cmp);
int sum=0;
int i=0;
double allVal=0;
for(i=0;i<s&&(sum+arr[i].weight)<=w;i++){
sum+=arr[i].weight;
allVal+=arr[i].value;
}
if(i<s)
allVal=allVal+(w-sum)*arr[i].single;
printf("%.2lf\n",allVal);
}
return 0;
}
-------------本文结束感谢您的阅读-------------
0%