On: Algorithms, A Dropbox Challenge and Dynamic Progra...

[btilly]

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:

  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 []

(I could easily make this more efficient.)

[klochner → btilly]

You obviously missed this part:

   Just like with any dynamic programming problem, we need to produce a matrix

very nice code, I found it much clearer than the blog post

The key intuition is that by considering the items sequentially, you only care about being able to reach a given sum rather than caring about all the subsets that can reach that sum. So the performance is linear in the number of different sums rather than the number of subsets.

[btilly → klochner]

No, I didn't miss that part. I just didn't believe it.

See http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_pro.... You will find that having a table is only one of several options. The approach that I took fits the description of the second class of technique there, going bottom up.

[klochner → btilly]

I was kidding :)

seriously though, what's up with the sort() call?

[btilly → klochner]

what's up with the sort() call?

The spec for the problem he was actually trying to solve said that you needed to provide the set of activities in sorted order. The list is generated in no particular order, so I sorted them before returning them. (A Python array sort sorts the array in place.)

[l0nwlf → btilly]

Could you link to those Project Euler problems, where you have been using this code ?

[btilly → l0nwlf]

Lots of project Euler problems have dp solutions. Try http://projecteuler.net/index.php?section=problems&id=21... for a fairly easy one, or http://projecteuler.net/index.php?section=problems&id=20... for a harder one.

Note that many others have dp solutions, but the easiest way to find them is to write a recursive function that you memoize. A good example of that is http://projecteuler.net/index.php?section=problems&id=30....