Dynamic programming fill 3D array
-
Hello, I'm trying to solve the 3 subset sum problem witch dynamic programming using a 3D array but I don't really now which rules to use to fill the array, can someone please help me to figure out the rules. Example (I need 3 subsets such that they have same sum) Input: {2,2,1,1} A = {2} B = {2} C = {1,1} Return: true How I understand it: With 3D array I'm searching if I can find 2 Subsets with sum = TotalSum/3 each. But how to fill the array, which rules should I use :confused:
int subSetsFound(int n, int set[], int sum1, int sum2) {
//n is n-1 (sum1 and sum2 are TotalSum/3)
//cuboid[n][i][j] tells whether first set can have sum i and second - sum j in set = n
int cuboid[sum1+1][sum2+1][n+1];// initialize top row/depth as true for (int i = 0; i <= n; i++) { cuboid\[0\]\[0\]\[i\] = 1; } // initialize two leftmost columns (one in depth), except cuboid\[0\]\[0\]\[0\] and cuboid\[0\]\[1\]\[0\], as 0 (false) for (int i = 1; i <= sum1; i++) { cuboid\[i\]\[0\]\[0\] = 0; cuboid\[0\]\[i\]\[0\] = 0; }
//not sure if I should do this
for (int i = 0; i <= sum1; i++) {
for (int j = 1; j <= sum2; j++) {
cuboid[0][j][i] = 0;
}
}for (int i = 1; i <= sum1; i++) { for (int j = 0; j <= sum2; j++) { for (int k = 1; k <= n; k++) { cuboid\[i\]\[j\]\[k\] = cuboid\[i\]\[j\]\[k-1\]; if (i - set\[k-1\] >= 0) cuboid\[i\]\[j\]\[k\] = cuboid\[i\]\[j\]\[k\] || cuboid\[ j-set\[k-1\] \] \[j\] \[k-1\]; /\* This is for 2-sub-set problem if (i-S\[j-1\]) >= 0 P(i, j) ← P(i, j-1) или P(i-S\[j-1\], j-1) P(i, j) ← P(i, j-1) \*/ } } } return cuboid\[sum1\]\[sum2\]\[n\];//first set have sum = sum1 and second sum = sum2, so there are two subsets such that the sum is equal