max dot product done

also known as maximize online ad revenue in exercise pdf file.

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