Algorithm Challenge II

Post Reply New Topic

Sort the square roots of the integers between 1 and 50 into two bins so as to minimize the difference between the sums of the bins.

Problem courtesy of Don Knuth. Solution appears (IIRC) in his paper "Are Toy Problems Useful?", published in his _Selected Papers on Computer Science_.

Best result I could find is 0.0000117092118046003 difference, there probably can be better ones. I used genetic algorithm so I guess I can never know.

first group: 1, 2, 3, 5, 6, 9, 12, 14, 16, 18, 21, 22, 23, 24, 28, 29, 32, 33, 34, 36, 37, 38, 41, 46, 48, 49
second group: 4, 7, 8, 10, 11, 13, 15, 17, 19, 20, 25, 26, 27, 30, 31, 35, 39, 40, 42, 43, 44, 45, 47, 50