summaryrefslogtreecommitdiff
path: root/PlaygroundCpp
diff options
context:
space:
mode:
authorHaidong Ji2018-09-07 16:03:50 -0500
committerHaidong Ji2018-09-07 16:03:50 -0500
commit91a1fa6d3069ca287a01f501c2ad3ad986f30ff7 (patch)
tree171d54e4d39ca7307ca581372d58f603309d58e0 /PlaygroundCpp
parentc6ad5d0aef9529a62e0786c97e8447c7d0f0db6a (diff)
Fractional Knapsack done.
Good exercise. Learned C++ vector usage, and the ASSERT_NEAR macro for testing floats/doubles. Lots of fun.
Diffstat (limited to 'PlaygroundCpp')
-rw-r--r--PlaygroundCpp/.settings/language.settings.xml4
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp99
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 &quot;${INPUTS}&quot;" 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 &quot;${INPUTS}&quot;" 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 &quot;${INPUTS}&quot;" 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 &quot;${INPUTS}&quot;" 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;
}