5 ms·

Algorithms, A Dropbox Challenge and Dynamic Programming

57 points by fukumoto 16y ago

btilly 16y ago
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 16y ago
  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 16y ago
    No, I didn't miss that part. I just didn't believe it. See http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming 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 16y ago
      I was kidding :) seriously though, what's up with the sort() call?
      - btilly 16y ago
        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 16y ago
  Could you link to those Project Euler problems, where you have been using this code ?
  - btilly 16y ago
    Lots of project Euler problems have dp solutions. Try http://projecteuler.net/index.php?section=problems&id=215 http://projecteuler.net/index.php?section=problems&id=21... for a fairly easy one, or http://projecteuler.net/index.php?section=problems&id=201 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=301 http://projecteuler.net/index.php?section=problems&id=30....
warrenwilkinson 16y ago
The challenge was: --- 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?
- xal 16y ago
  Hehe yes, and I feel kinda bad for that. I think it's some permanent damage that I picked up from pair programming using unit tests and my desire to troll my pair partner into doing all the actual typing.
Stormbringer 16y ago
I have a proof that P=NP, but the margin is too small to contain it
NY_USA_Hacker 16y ago
So, for the problem, we are given some positive integer n and, for i = 1, 2, ..., n, numbers a(i). 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 this is a 0-1 integer quadratic program with one linear constraint. 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.
dmn001 16y ago
Here is my Perl code for the diet puzzle, as well as sorting it splits the set into positive and negative subsets: https://gist.github.com/805894 https://gist.github.com/805894
ttsiodras 16y ago
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: http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html

57 points by fukumoto 16y ago

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 16y ago
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 16y ago
  No, I didn't miss that part. I just didn't believe it. See http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming 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 16y ago
    I was kidding :) seriously though, what's up with the sort() call?
    - btilly 16y ago
      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 16y ago
Could you link to those Project Euler problems, where you have been using this code ?
- btilly 16y ago
  Lots of project Euler problems have dp solutions. Try http://projecteuler.net/index.php?section=problems&id=215 http://projecteuler.net/index.php?section=problems&id=21... for a fairly easy one, or http://projecteuler.net/index.php?section=problems&id=201 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=301 http://projecteuler.net/index.php?section=problems&id=30....

warrenwilkinson 16y ago

The challenge was: --- 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?

xal 16y ago
Hehe yes, and I feel kinda bad for that. I think it's some permanent damage that I picked up from pair programming using unit tests and my desire to troll my pair partner into doing all the actual typing.

Stormbringer 16y ago

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

NY_USA_Hacker 16y ago

So, for the problem, we are given some positive integer n and, for i = 1, 2, ..., n, numbers a(i). 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 this is a 0-1 integer quadratic program with one linear constraint. 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.

dmn001 16y ago

Here is my Perl code for the diet puzzle, as well as sorting it splits the set into positive and negative subsets: https://gist.github.com/805894 https://gist.github.com/805894

ttsiodras 16y ago

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: http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html