-
Notifications
You must be signed in to change notification settings - Fork 2
/
Fractional Knapsack
46 lines (43 loc) · 1.04 KB
/
Fractional Knapsack
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
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
struct knap{
//int v,w;
double v,w,vw;
};
bool comp(knap k1, knap k2){
return (k1.vw<k2.vw);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n ;
double weight;
cin >> n >> weight;
knap arr[n];
for(int i=0;i<n;i++) {
cin >> arr[i].v >> arr[i].w;
arr[i].vw=arr[i].v/arr[i].w;
}
double val=0.0;
sort(arr,arr+n,comp);
//for(int i=n-1;i>=0;i--) cout << arr[i].v << " " << arr[i].w<< " ";
for(int i=n-1;i>=0 && weight>0;i--){
if(arr[i].w<=weight){
val += arr[i].v;
weight -= arr[i].w;
//cout << " " << val << endl;
}
else{
val+=arr[i].v*(double)((double)weight/arr[i].w);
weight=0;
//cout << " " << val << endl;
break;
}
}
printf("%.2f\n",val);
//cout << setprecision(2) << val << endl;
}
return 0;
}