I have to solve a classic partition problem using dynamic programming. I have an array of positive integers as an input where n is the number of integers and s is the sum of those integers, and I need to find the minimum difference between two sets that can be constructed using elements from input. I also need to output an boolean array called "ownership" of the same size as input array, which provides information if the elements belong to the first or second optimal set. For example, if i-th value in the ownership array is true then the i-th element of the input array belongs to the first set.
My program finds minimum difference using bottom-up approach. The task requires that the memory complexity of the program is θ(s), so instead of using 2D array of size n*s like in classical approach, I'm using only two rows of that array. In the first row I keep the previous processed row, so I can fill the second row basing on the previous solutions.
The problem is that with this memory optimization I'm not sure how I should fill the ownership array.
I know that one could retrieve the set elements using backtracking in n*s array. However, because of the task constraints, I cannot use that method and I have no idea on how I could efficiently construct ownership table.
Is there a way to efficiently find which elements belong to which of those two optimal sets, with constraint of memory complexity θ(s) and time complexity O(n*s) in the bottom-up approach?
My current code in C#:
public int SetsMinimum(int[] tab, out bool[] ownership)
{
int n = tab.Length;
int sum = 0;
foreach (int v in tab) sum += v;
ownership = new bool[n];
bool[,] dp = new bool[2, sum + 1];
int min = sum;
dp[0, 0] = true;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
dp[1,j] = dp[0,j];
if (j - tab[i - 1]>=0)
{
dp[1, j] = dp[0, j - tab[i - 1]];
}
}
for(int j=0;j<sum;j++)
{
if (dp[1, j])
{
int cMin = Math.Abs((sum - j) - j);
if (min>cMin)
{
min = cMin;
}
}
dp[0, j] = dp[1, j];
}
}
return min;
}
I found a solution yesterday:
sum+1
elements and fill it with zeroes.{4,3,2}
you could achieve sum 7 when you used second element, and you could get sum of 4
with the first element.(sum-min)/2
, or sum-((sum-min)/2)
.This approach will only pick neccesary elements to construct either one of sets sum, and it will work in O(n*s) time since the index array can be filled during bottom-up approach.