0

Possible Duplicate:
divide an array into two sets with minimal difference

What can be an optimized algorithm to divide an array of numbers such that the difference of sum of the numbers of resultant arrays is minimum. The difference of number of elements in the two arrays can be at maximum one.

Community
  • 1
  • 1
Shashwat Kumar
  • 5,159
  • 2
  • 30
  • 66
  • 1
    This is not identical qustion, because in here there is an extra constraint on the two parts size. This problem is still NP-Hard, but it is not *exactly* the partition problem. – amit Nov 18 '11 at 14:30
  • @amit: The extra constraint does not change much, since the array might have n zeroes at the beginning, and in every division of array the zeroes can be moved to satisfy the constraint, without affecting the sum. – sdcvvc Nov 18 '11 at 16:44
  • @sdcvvc: I partially agree. I mentioned, it still is NP-Hard, but it reqiures an explanation [reduction] why it is basically the same problem. The reduction in here is indeed padding the array with extra zeros. – amit Nov 18 '11 at 23:05

0 Answers0