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 <gtest/gtest.h>
using std::vector;
static int getBestItem(vector<int> values, vector<int> weights) {
double maxValuePerWeight = 0;
int bestItem = 0;
for (int i = 0; i < weights.size(); i++) {
if (weights[i] > 0) {
if ((double) values[i] / weights[i] > maxValuePerWeight) {
maxValuePerWeight = (double) values[i] / weights[i];
bestItem = i;
}
}
}
return bestItem;
}
static double getOptimalValueNaive(int capacity, vector<int> values, vector<int> weights) {
double totalValue = 0;
int tempWeight = 0;
for (int i = 0; i < weights.size(); i++) {
if (capacity == 0)
return totalValue;
int j = getBestItem(values, weights);
if (weights[j] < capacity)
tempWeight = weights[j];
else
tempWeight = capacity;
totalValue = totalValue
+ tempWeight * ((double) values[j] / weights[j]);
weights[j] = weights[j] - tempWeight;
capacity = capacity - tempWeight;
}
return totalValue;
}
//TEST(FractionalKnapsack, BestItem1) {
// vector<int> values = { 60, 100, 120 };
// vector<int> weights = { 20, 50, 30 };
// ASSERT_EQ(getBestItem(values, weights), 2);
//}
//
//TEST(FractionalKnapsack, BestItem2) {
// vector<int> values = { 120 };
// vector<int> weights = { 30 };
// ASSERT_EQ(getBestItem(values, weights), 0);
//}
//
//TEST(FractionalKnapsack, OptimalValue1) {
// vector<int> values = { 60, 100, 120 };
// vector<int> weights = { 20, 50, 30 };
// int capacity = 50;
// ASSERT_DOUBLE_EQ(getOptimalValueNaive(capacity, values, weights), 180.0);
//}
//
//TEST(FractionalKnapsack, OptimalValue2) {
// vector<int> values = { 500 };
// vector<int> weights = { 30 };
// int capacity = 10;
// ASSERT_NEAR(getOptimalValueNaive(capacity, values, weights), 166.6667, 0.0001);
//}
//
//TEST(FractionalKnapsack, OptimalValue3) {
// vector<int> values = { 44,26,31 };
// vector<int> weights = { 6,28,38 };
// int capacity = 50;
// ASSERT_NEAR(getOptimalValueNaive(capacity, values, weights), 83.0526, 0.0001);
//}
int main() {
int n;
int capacity;
std::cin >> n >> capacity;
vector<int> values(n);
vector<int> weights(n);
for (int i = 0; i < n; i++) {
std::cin >> values[i] >> weights[i];
}
double optimal_value = getOptimalValueNaive(capacity, values, weights);
std::cout.precision(10);
std::cout << optimal_value << std::endl;
return 0;
}
|
