From b9808ba0d4ff582a30f3a407fb11078232797009 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 27 Dec 2018 10:38:46 -0600
Subject: Knapsack partition3 done!

---
 PlaygroundCpp/Sources/Playground.cpp | 61 +++++++++++++++++++++++++++---------
 1 file changed, 46 insertions(+), 15 deletions(-)

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 50297b2..3083cdc 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -4,10 +4,10 @@
 
 using std::vector;
 
-int optimalWeight(int W, vector<int> &w2) {
+vector<vector<int>> optimalWeight2DArray(int W, vector<int> &w2) {
 	int j = w2.size();
 //	int value[W + 1][j + 1];
-	vector< vector<int> > value(W + 1, vector<int>(j + 1));
+	vector<vector<int> > value(W + 1, vector<int>(j + 1));
 
 	for (int i = 0; i < j + 1; i++) {
 		for (int w = 0; w < W + 1; w++) {
@@ -25,22 +25,53 @@ int optimalWeight(int W, vector<int> &w2) {
 		}
 
 	}
-	return value[W][j];
+	return value;
 }
 
-//TEST(Knapsack, t1) {
-//	vector<int> w = { 1, 4, 8 };
-//	int W = 10;
-//	ASSERT_EQ(9, optimalWeight(W, w));
+int partition3(vector<int> &a) {
+	if (a.size() < 3)
+		return 0;
+	int sum = 0;
+	for (int i = 0; i < a.size(); i++) {
+		sum = sum + a[i];
+	}
+	if (sum % 3 != 0)
+		return 0;
+	int W = sum / 3;
+	vector<vector<int> > values = optimalWeight2DArray(W, a);
+	int count = 0;
+	for (int i = 1; i < a.size() + 1; i++) {
+		for (int w = 1; w < W + 1; w++) {
+			if (values[w][i] == W)
+				count = count + 1;
+		}
+	}
+	if (count >= 3)
+		return 1;
+	else
+		return 0;
+}
+//TEST(KnapsackPartition3, t1) {
+//	vector<int> a = { 3, 3, 3, 3 };
+//	ASSERT_EQ(0, partition3(a));
+//}
+//
+//TEST(KnapsackPartition3, t2) {
+//	vector<int> a = { 30 };
+//	ASSERT_EQ(0, partition3(a));
+//}
+//
+//TEST(KnapsackPartition3, t3) {
+//	vector<int> a = { 1, 2, 3, 4, 5, 5, 7, 7, 8, 10, 12, 19, 25 };
+//	ASSERT_EQ(1, partition3(a));
 //}
 
 int main() {
-  int n, W;
-  std::cin >> W >> n;
-  vector<int> w(n);
-  for (int i = 0; i < n; i++) {
-    std::cin >> w[i];
-  }
-  std::cout << optimalWeight(W, w) << '\n';
+	int n;
+	std::cin >> n;
+	vector<int> A(n);
+	for (size_t i = 0; i < A.size(); ++i) {
+		std::cin >> A[i];
+	}
+	std::cout << partition3(A) << '\n';
 }
-
-- 
cgit v1.2.3