Personal tools

Dynamic programming example

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Creation and first example)

Revision as of 04:06, 11 April 2007


Dynamic programming refers to translating a problem to be solved into a recurrence formula, and crunching this formula with the help of an array (or any suitable collection) to save useful intermediates and avoid redundant work.

Computationally, dynamic programming boils down to write once, share and read many times. This is exactly what lazy functional programming is for.

1 Sample problems and solutions

1.1 Available in 6-packs, 9-packs, 20-packs

A fast food place sells a finger food in only boxes of 6 pieces, boxes of 9 pieces, or boxes of 20 pieces. You can only buy zero or more such boxes. Therefore it is impossible to buy exactly 5 pieces, or exactly 7 pieces, etc. Can you buy exactly N pieces?

If I can buy i-6 pieces, or i-9 pieces, or i-20 pieces (provided these are not negative numbers), I can then buy i pieces (by adding a box of 6 or 9 or 20). Below, I set up the array
r
for exactly that, with
r!0
forced to
True
to bootstrap the whole thing.
import Data.Array
 
buyable n = r!n
    where r = listArray (0,n) (True : map f [1..n])
          f i = i >= 6 && r!(i-6) || i >= 9 && r!(i-9) || i >= 20 && r!(i-20)