diff options
Diffstat (limited to 'PlaygroundCpp')
| -rw-r--r-- | PlaygroundCpp/.settings/language.settings.xml | 4 | ||||
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 99 |
2 files changed, 75 insertions, 28 deletions
diff --git a/PlaygroundCpp/.settings/language.settings.xml b/PlaygroundCpp/.settings/language.settings.xml index 54c9fee..bbdba31 100644 --- a/PlaygroundCpp/.settings/language.settings.xml +++ b/PlaygroundCpp/.settings/language.settings.xml @@ -11,7 +11,7 @@ <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939556362312027581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939399062786427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> @@ -33,7 +33,7 @@ <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939556362312027581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939399062786427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index fbda74a..025da48 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,43 +1,90 @@ #include <iostream> +#include <vector> //#include <gtest/gtest.h> -static int getNumOfCoins(int m) { - // coins with denominations of 1, 5, and 10 - int coinCount = 0; - int remainder; - if (m / 10 == 0 && m % 10 == 0) - return m / 10; - coinCount = coinCount + m / 10; - remainder = m % 10; - if (remainder >= 5) - return coinCount + 1 + remainder - 5; - else - return coinCount + remainder; +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(ChangingMoney, One) { -// ASSERT_EQ(getNumOfCoins(1), 1); +//TEST(FractionalKnapsack, BestItem1) { +// vector<int> values = { 60, 100, 120 }; +// vector<int> weights = { 20, 50, 30 }; +// ASSERT_EQ(getBestItem(values, weights), 2); //} // -//TEST(ChangingMoney, Two) { -// ASSERT_EQ(getNumOfCoins(2), 2); +//TEST(FractionalKnapsack, BestItem2) { +// vector<int> values = { 120 }; +// vector<int> weights = { 30 }; +// ASSERT_EQ(getBestItem(values, weights), 0); //} // -//TEST(ChangingMoney, Six) { -// ASSERT_EQ(getNumOfCoins(6), 2); +//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(ChangingMoney, TwentyEight) { -// ASSERT_EQ(getNumOfCoins(28), 6); +//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(ChangingMoney, OneThousand) { -// ASSERT_EQ(getNumOfCoins(1000), 100); +//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 m; - std::cin >> m; - int c = getNumOfCoins(m); - std::cout << c << '\n'; + 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; } |