The Problem
Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {1,2,...,n} such that |Sx-Sy| is minimum, where Sx and Sy are the sums of the elements in X and Y. i.e., if A=[1,3,1,1], then X={1,3,4} and Y={2} and the solution is optimal with Sx=3, Sy=3, |Sx-Sy|=0.
My Solution (In pseudocode)
For i=0 to n
if A[i]==K //If this element is the highest element in the array, put it in Sy
Sy.add(A[i])
Else if A[i]=/=0 //We don't care about zeroes, the rest goes in Sx
Sx.add(A[i])
min = |Sx-Sy| //Calculate our min as it is
DO
go=false
//Move the smallest element from the biggest group to the other one
if Sx>Sy
SyTemp = Sy + min(Sx)
SxTemp = Sx - min(Sx)
else if Sy>Sx
SxTemp = Sx + min(Sy)
SyTemp = Sy - min(Sy)
//if this improves on our min, save it and check for another iteration
if |SxTemp-SyTemp|<min
Sx=SxTemp
Sy=SyTemp
min = |Sx-Sy|
go=true
else
Return Sx,Sy //if the new sets are worse than the ones before, return the old ones
While(go)
My question
Apparently, this problem is NP complete (At least that is what my professor told me), and my question comes from the way he scored my solution. I got 3 points out of 9 because a dynamic programming solution is what was requested - while this is a greedy approach - and my solution has edge cases in which it won't work.
the example he gave me to prove that these edge cases exist was [1,2,5,5] and he said that in this case the algorithm would return {1,2,5},{5} instead of {1,5},{2,5}. Now, to me it seems like my solution would actually return what he wants, and I can't really think of an example this algorithm couldn't deal with, so I'm here to ask the community if you see any errors in my solution, if you think my professor is right in saying that his example wouldn't be solved optimally (or that there are edge cases in which this approach won't work), and if you think this will perform better than O(K(n^2)), where K is the sum of all values of the array (which apparently is the time complexity of his DP solution).
For i=0 to n
if A[i]==K
$\endgroup$ – user12859 Feb 10 '17 at 19:39i=0
,i
is not a valid index toA
. $\endgroup$ – user12859 Feb 10 '17 at 20:31