Algorithms, A Dropbox Challenge and Dynamic Programming
skorks.com
skorks.com
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 []
Just like with any dynamic programming problem, we need to produce a matrix
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.
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.
seriously though, 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.)
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....
---
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.
---
Did anyone else here immediately think to write a function hard coded to return the empty set?
So, we seek x(i) to solve
min ( x(1) a(1) + x(2) a(2) + ... + x(n) a(n) )^2
x(1) + x(2) + ... + x(n) >= 0
subject to x(i) = 0, 1
So for a reasonably practical solution, omit the 0-1 constraint and attack the problem as just a quadratic program.
Then for the 0-1 constraint, do standard branch and bound.