>A question that I posed to a colleague, and passed onto the list, was the >task of splitting a set of 200 numbers into two sets that had the same sum. > >I claimed that it is unsolvable, in practice, since there is no efficient >algorithm, other than testing a huge number of cases (I suggested on the >order of 200 C 100). > >Two of the respondents have indicated that this problem is NP-Complete, and >hence the number of operations rises exponentially compared to the number of >values given. Given this, for a large enough set, the problem is >effectively unsolvable. So the question becomes, is 200 values sufficiently >large? > >Here is the test. > >The number below have a total of 10 000 000. Can you split it into two sets >that each have a sum of 5 000 000? I generated this list using Excel, so >there _is_ an answer, that currently only I know. Shane, me old mate, good >luck! > >BTW, this whole thing arose out of a grade 8 problem on putting 9 songs onto >the two sides of a cassette tape. > >Cheers > >Rex > Nmbers deleted
Well, it took less than a second what with putting the stuff on the screen. However, I don't have the right answer it seems. Optimization probs are like that sometimes because of the algorithm. One problem might be I don't switch unless I improve an estimate. It would be interesting to see if this is indeed the problem, but probably I need to sit down and think about the math. Enclosed are my numbers.