summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-09-07 21:43:31 -0500
committerHaidong Ji2018-09-07 21:43:31 -0500
commit81a53382da84d0bb85d2530c02644e6937075586 (patch)
treef70f9b79025a33dea89c35efe9b84d7efccb6548
parent91a1fa6d3069ca287a01f501c2ad3ad986f30ff7 (diff)
max dot product done
also known as maximize online ad revenue in exercise pdf file.
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp101
1 files changed, 29 insertions, 72 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 025da48..e79d68e 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,90 +1,47 @@
#include <iostream>
#include <vector>
+#include <algorithm>
//#include <gtest/gtest.h>
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;
- }
- }
+static long getMaxDotProduct(vector<int> a, vector<int> b) {
+ std::sort(a.begin(), a.end());
+ std::sort(b.begin(), b.end());
+ long result = 0;
+ for (int i = 0; i < b.size(); i++) {
+ result = (long) a[i]*b[i]+result;
}
- return bestItem;
+ return result;
}
-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(FractionalKnapsack, BestItem1) {
-// vector<int> values = { 60, 100, 120 };
-// vector<int> weights = { 20, 50, 30 };
-// ASSERT_EQ(getBestItem(values, weights), 2);
-//}
-//
-//TEST(FractionalKnapsack, BestItem2) {
-// vector<int> values = { 120 };
-// vector<int> weights = { 30 };
-// ASSERT_EQ(getBestItem(values, weights), 0);
+//TEST(MaxDotProduct, Max1) {
+// vector<int> a = { 60, 100, 120 };
+// vector<int> b = { 20, 50, 30 };
+// ASSERT_EQ(getMaxDotProduct(a, b), 10200);
//}
//
-//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(MaxDotProduct, Max2) {
+// vector<int> a = { 23 };
+// vector<int> b = { 39 };
+// ASSERT_EQ(getMaxDotProduct(a, b), 897);
//}
//
-//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(MaxDotProduct, Max3) {
+// vector<int> a = { 1,3,-5 };
+// vector<int> b = { -2,4,1 };
+// ASSERT_EQ(getMaxDotProduct(a, b), 23);
//}
-//
-//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 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];
+ size_t n;
+ std::cin >> n;
+ vector<int> a(n), b(n);
+ for (size_t i = 0; i < n; i++) {
+ std::cin >> a[i];
}
-
- double optimal_value = getOptimalValueNaive(capacity, values, weights);
-
- std::cout.precision(10);
- std::cout << optimal_value << std::endl;
- return 0;
+ for (size_t i = 0; i < n; i++) {
+ std::cin >> b[i];
+ }
+ std::cout << getMaxDotProduct(a, b) << std::endl;
}