From 91a1fa6d3069ca287a01f501c2ad3ad986f30ff7 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 7 Sep 2018 16:03:50 -0500
Subject: Fractional Knapsack done.
Good exercise. Learned C++ vector usage, and the ASSERT_NEAR macro for
testing floats/doubles. Lots of fun.---
PlaygroundCpp/.settings/language.settings.xml | 4 +-
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 @@
-
+
@@ -33,7 +33,7 @@
-
+
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
+#include
//#include
-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 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(ChangingMoney, One) {
-// ASSERT_EQ(getNumOfCoins(1), 1);
+//TEST(FractionalKnapsack, BestItem1) {
+// vector values = { 60, 100, 120 };
+// vector weights = { 20, 50, 30 };
+// ASSERT_EQ(getBestItem(values, weights), 2);
//}
//
-//TEST(ChangingMoney, Two) {
-// ASSERT_EQ(getNumOfCoins(2), 2);
+//TEST(FractionalKnapsack, BestItem2) {
+// vector values = { 120 };
+// vector weights = { 30 };
+// ASSERT_EQ(getBestItem(values, weights), 0);
//}
//
-//TEST(ChangingMoney, Six) {
-// ASSERT_EQ(getNumOfCoins(6), 2);
+//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(ChangingMoney, TwentyEight) {
-// ASSERT_EQ(getNumOfCoins(28), 6);
+//TEST(FractionalKnapsack, OptimalValue2) {
+// vector values = { 500 };
+// vector 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 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 m;
- std::cin >> m;
- int c = getNumOfCoins(m);
- std::cout << c << '\n';
+ 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;
}
--
cgit v1.2.3