Problem Statement:-
You and two of your friends have just returned back home after visiting various countries. Now you would
like to evenly split all the souvenirs that all three of you bought.
Problem Description
Input Format. The first line contains an integer n. The second line contains integers v 1 , v 2 , . . . , v n separated
by spaces.
Constraints. 1 ≤ n ≤ 20, 1 ≤ v i ≤ 30 for all i.
Output Format. Output 1, if it possible to partition v 1 , v 2 , . . . , v n into three subsets with equal sums, and
0 otherwise.
My Approach:
My approach is very similar to the knapsack problem, however, instead of filling in only one knapsack, we fill two knapsacks each with capacity sum/3, and try to maximize the weight in it.
The answer is true when dp[n][sum/3][sum/3]==2*sum/3.
An item has three choice:
- dp[i][j][k]= dp[i-1][j][k]
- dp[i][j][k]=dp[i-1][j-a[i]][k] +a[I]
- dp[i][j][k]=dp[i-1][j][k-a[I]] + a[I]
For the base case, I initialized the 3-dimensional array to have value 0.
However, it’s not performing as expected, it’s giving the wrong answer for this case:-
Input:
5
1 6 4 3 7
Expected output:
1 // here we divide it such as {1,6}, {4,3} ,{7}
Output using the below implementation:
0
Can I get some help in figuring out the bug? Thanks in advance.
PS: There might some concerns over the issue of StackOverflow using variable length array in C++, but I request you to just help me improve my logic part of the implementation.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int arr[n + 1];
int sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
sum += arr[i];
}
int par = sum / 3;
//forming a DP solution with 3 states.
//More precisely, trying to replicate the classic knapsack problem
//, where we have two knapsacks each of capacity sum/3.
//Now we try to maximaze the items in these knapsacks.
int dp[n + 1][par + 1][par + 1];
//for the base case
memset(dp, 0, sizeof(dp));
//using bottom-up Dynamic Programming
if (sum % 3 == 0)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= par; j++)
{
for (int k = 1; k <= par; k++)
{
//the item may not contain in both two knapsacks
//in this case it falls in the 3rd Knapsack
dp[i][j][k] = dp[i - 1][j][k];
//keeping the item in the first knapsack
if (j >= arr[i])
dp[i][j][k] = max(dp[i - 1][j - arr[i]][k] + arr[i], dp[i][j][k]);
//keeping the item in the second knapsack
if (k >= arr[i])
dp[i][j][k] = max(dp[i - 1][j][k - arr[i]] + arr[i], dp[i][j][k]);
}
}
}
//since both the knapsacks have max capacity of sum/3
if(dp[n][par][par]==2*sum/3)
cout << 1 << endl;
else
cout << 0 << endl;
}
else
{
cout << 0 << endl;
}
return 0;
}