Sums of sets

Two more programming puzzles.

You want to partition sqrt(1), sqrt(2), ..., sqrt(n) into two sets that minimize the difference of the sums. What's the best complexity you can get?

And one via David Eppstein. (Don't look unless you want a big hint.) "Let S be a set (or multiset) of positive integers. Describe an efficient algorithm for finding the smallest positive integer x such that x is not the sum of some subset of S."