Fractional Knapsack done.

Good exercise. Learned C++ vector usage, and the ASSERT_NEAR macro for
testing floats/doubles. Lots of fun.

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;
 }