diff options
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 61 |
1 files 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'; } - |