Alex Rivera | Logout

Can bottom-up dynamic programming be done in Lisp?

Asked 2011-10-19T16:38:04.100
11

Can a typical Lisp dialect solve problems using the bottom-up "dynamic programming" approach?

(Please note: I'm not talking about "memoization" which, as far as I understand, is trivial using any Lisp dialect. I'm really talking about bottom-up Dynamic Programming, where you build, for an example, your array bottom up and then use the elements you just introduced to compute the next ones.)

For example, using dynamic programming, the "0-1 knapsack" problem can be solved in pseudo-polynomial time for inputs on which any other method would fail.

An imperative (incomplete) solution is:

for (int k = 1; k <= a.length; k++) {
    for (int y = 1; y <= b; y++) { 
        if (y < a[k-1]) {
            knap[k][y-1] = knap[k-1][y-1];
        } else {
            if (y > a[k-1]) {
                knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
            } else {
                knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
    }
}

Is such a thing possible to do in the various Lisp dialects? If no, why not?

algorithm clojure lisp dynamic-programming knapsack-problem
Edit
Report

2 Answers

4

Pardon me for saying this, but the wikipedia page you refer to is (imnsho) not very well-written. In particular, it more or less fabricates the dichotomy between top-down and bottom-up dynamic programming, and goes on to describe one as "more interesting". The only difference between the two is the order in which the table is constructed. Memoization gives rise to both of these, depending on the order in which the calls are made.

Apologies in advance to whoever wrote this section of the page; I appreciate your effort, I just think that the section needs some work.

answered 2011-10-19T17:01:25.753
2

Here's a nice bottom-up version of Fibonacci in Clojure (originally written by Christophe Grand, I believe):

(defn fib []
  (map first (iterate
              (fn [[a b]] [b (+ a b)])
              [0 1])))

This generates an infinite lazy sequence, so you can ask for as much or as little as you like:

(take 10 (fib))
=> (0 1 1 2 3 5 8 13 21 34)

(nth (fib) 1000)
=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
answered 2011-10-19T20:26:01.703

Your Answer