## COS 226 Programming Assignment 9

## Subset sums

Consider the square roots of the numbers from 1 to 100. Write a program
to divide them into two sets A and B having the property that the sum of the
numbers in set A is as close as possible to the sum of the numbers in set B.
Unlike previous programming assignments, there is no algorithm given
in the book for this problem, nor will one be recommended here.
Indeed, this is an NP-complete problem, so that finding the best
possible answer would seem to require checking all possibilities. On
the other hand, there are many heuristics that can lead to good
answers, especially if efficient algorithmic tools are used. Depending
on the heuristics that you choose, you may need to implement a sorting
routine, hash table, search tree, priority queue, trie, or some other
data structure that you have learned.

Use double-precision floating-point numbers in calculating the square roots
and the subset sums.

If you make use of certain mathematical facts in the development of your
solution, be sure that you state them, along with some justification, in
your writeup. It is not necessary for you to provide proofs; something
that you think might be true might be a heuristic that leads to a good
solution, even if you can't prove it.

Your program should first print the difference in the sums of the subsets
on the first line, then the numbers (not their square roots) in the set
containing 1 on subsequent lines, 15 per line.

Your task is not only to design and implement an algorithm for this problem,
but also to exercise good judgment in consuming CPU cycles and, as usual,
providing a convincing explanation of your method and rationale for
important design and implementation decisions.