-
Notifications
You must be signed in to change notification settings - Fork 0
/
fractional-knapsack.cpp
90 lines (73 loc) · 1.76 KB
/
fractional-knapsack.cpp
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Data class for storage
class Data {
public:
float value; // given value
float weight; // given quantity
float avg; // value per quantity
// constructor
Data(float val, float wt) {
value = val;
weight = wt;
avg = (val/wt);
}
};
// comaparator function for sorting
bool compareData(Data *left, Data *right) {
return (left->avg > right->avg);
}
float fractionalKnapsack(vector<float> &vals, vector<float> &wts, int n, float maxLimit) {
// declare data
vector<Data*> data(n);
// initialize data
for(int i=0; i<n; i++) {
data[i] = new Data(vals[i], wts[i]);
}
// sort it in descending order
sort(data.begin(), data.end(), compareData);
// result
float total = 0;
// iterate over data
for(int i=0; i<n; i++) {
// if limit == 0 break
if(maxLimit == 0)
break;
Data *curr = data[i];
// if weight is greater than or equal to maxLimit
// use it as a whole
if((maxLimit - curr->weight) >= 0) {
total += curr->value;
maxLimit -= curr->weight;
}
// otherwise use its fraction
else {
total += maxLimit*curr->avg;
maxLimit = 0;
}
}
// return result
return total;
}
int main() {
int n;
cin>>n;
// input values
vector<float> v(n);
for(int i=0; i<n; i++) {
cin>>v[i];
}
// input weights
vector<float> w(n);
for(int i=0; i<n; i++) {
cin>>w[i];
}
// input limit
float limit;
cin>>limit;
// find and print output
float result = fractionalKnapsack(v, w, n, limit);
cout<<result;
}