Menu
Given a set of numbers, divide the numbers into two subsets such that difference between the sum of numbers in two subsets is minimal.
This is the idea that I have, but I am not sure if this is a correct solution:
Is this the correct solution? Can we do better?
572
To find Minimum sum difference, w have to find j such that Min{sum - j*2 : dp[n][j] == 1 } where j varies from 0 to sum/2 The idea is, sum of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to sum.
The SUBSET-SUM problem involves determining whether or not a subset from a list of integers can sum to a target value. For example, consider the list of nums = [1, 2, 3, 4] . If the target = 7 , there are two subsets that achieve this sum: {3, 4} and {1, 2, 4} . If target = 11 , there are no solutions.
The decision version of the problem you are describing is an NP-complete problem and it is called the partition problem. There are a number of approximations which provide, in many cases, optimal or, at least, good enough solutions.
The simple algorithm you described is a way playground kids would pick teams. This greedy algorithm performs remarkably well if the numbers in the set are of similar orders of magnitude.
The article The Easiest Hardest Problem, by American Scientist, gives an excellent analysis of the problem. You should go through and read it!
130
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
