Algorithms, A Dropbox Challenge and Dynamic Programming

That is a very complicated way to code this. Here is the quick and dirty technique that I have been using on lots of Project Euler problems:<p><pre><code> def subset_summing_to_zero (activities): subsets = {0: []} for (activity, cost) in activities.iteritems(): old_subsets = subsets subsets = {} for (prev_sum, subset) in old_subsets.iteritems(): subsets[prev_sum] = subset new_sum = prev_sum + cost new_subset = subset + [activity] if 0 == new_sum: new_subset.sort() return new_subset else: subsets[new_sum] = new_subset return [] </code></pre> (I could easily make this more efficient.)

The challenge was:<p>---<p>We get a list of up to 50 activities and an associated calorie value for each (either positive or negative), we need to find a subset of activities where the sum of all the calorie values is zero.<p>---<p>Did anyone else here immediately think to write a function hard coded to return the empty set?

I did a very similar investigation 5 years ago, to find the optimal way to fill-up a DVD from a set of files of various sizes (more than a DVD's worth). Have a look:<p><a href="http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html" rel="nofollow">http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html</a>

Here is my Perl code for the diet puzzle, as well as sorting it splits the set into positive and negative subsets: <a href="https://gist.github.com/805894" rel="nofollow">https://gist.github.com/805894</a>

So, for the problem, we are given some positive integer n and, for i = 1, 2, ..., n, numbers a(i).<p>So, we seek x(i) to solve<p><pre><code> min ( x(1) a(1) + x(2) a(2) + ... + x(n) a(n) )^2 x(1) + x(2) + ... + x(n) &#62;= 0 subject to x(i) = 0, 1 </code></pre> So this is a 0-1 integer quadratic program with one linear constraint.<p>So for a reasonably practical solution, omit the 0-1 constraint and attack the problem as just a quadratic program.<p>Then for the 0-1 constraint, do standard branch and bound.

I have a proof that P=NP, but the margin is too small to contain it