#include #include //#include using std::vector; static int getBestItem(vector values, vector 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 values, vector 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 values = { 60, 100, 120 }; // vector weights = { 20, 50, 30 }; // ASSERT_EQ(getBestItem(values, weights), 2); //} // //TEST(FractionalKnapsack, BestItem2) { // vector values = { 120 }; // vector weights = { 30 }; // ASSERT_EQ(getBestItem(values, weights), 0); //} // //TEST(FractionalKnapsack, OptimalValue1) { // vector values = { 60, 100, 120 }; // vector weights = { 20, 50, 30 }; // int capacity = 50; // ASSERT_DOUBLE_EQ(getOptimalValueNaive(capacity, values, weights), 180.0); //} // //TEST(FractionalKnapsack, OptimalValue2) { // vector values = { 500 }; // vector weights = { 30 }; // int capacity = 10; // ASSERT_NEAR(getOptimalValueNaive(capacity, values, weights), 166.6667, 0.0001); //} // //TEST(FractionalKnapsack, OptimalValue3) { // vector values = { 44,26,31 }; // vector 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 values(n); vector 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; }