Hugh Perkins hughperkins at gmail.com
Mon Aug 6 05:26:32 EDT 2007

```There's a neat Haskell solution to the knapsack problem which runs very
fast.  I'm not 100% sure that it runs faster than an optimal solution in
other GC'd imperative languages, but it's very concise and not (too)
convoluted.  Have a search for the thread with "xkcd" in the title.

Chung-chieh Shan wrote:

Here's my solution to the xkcd problem (yay infinite lists):

xkcd_c287' = foldr
(\cost without ->
let (poor, rich) = splitAt cost without
with = poor ++ zipWith (++) rich (map (map (cost:)) with)
in with)
([[]] : repeat [])
[215, 275, 335, 355, 420, 580] -- [2, 4, 150001]
!!
1505 -- 150005

quickly.

Explication of how it works from "haskell at list.mightyreason.com":

I will jump in and explain, using a more finely named version:

xkcd_c287' = foldr
(\cost without ->
let (poor, rich) = splitAt cost without
with = poor ++ zipWith (++) rich using_cost
using cost = (map (add_cost) with)
in with)
([[]] : repeat [])
[215, 275, 335, 355, 420, 580] -- [2, 4, 150001]
!!
1505 -- 150005

At the top level it uses (!!) to pick the 1505th element of the list
produced by
the use of foldr.

foldr <function to combine new value with previous result>
<seed result>
<list of new values>

Here the list of new values is the list of item prices (in pennies) from the

The seed result is the answer in the absence of anything on the menu.

The seed is ([[]] : repeat []) which is a list of (list of prices).  The "n
th"
member of the outer list holds the solution for a price of "n pennies".

Thus the (!! 1505) selects the answer for a target price of \$15.05.

The seed result has an empty list in the 0th position since ordering nothing
is
a solution to a target price of \$0.00.

The function works as follows:
>         (\cost without ->

The 'cost' is the price of the new item on the menu.
The 'without' is the answer taking into account all previously processed
items
on the menu (before the 'cost' item).
The result will be a new answer taking into account 'cost' as well.

>             let (poor, rich) = splitAt cost without

The items in the old answer 'without' before the index 'cost' are solutions
for
a target price cheaper than 'cost' and these are in the 'poor' list.  These

The items in the 'rich' part of the answer may get new solutions that
include
ordering the new 'cost' item.

>                 with = poor ++ zipWith (++) rich using_cost
>                 using cost = (map add_cost with)
>                   where add_cost xs = cost:xs
>             in with)

The new answer will be 'with' which is defined recursively.

The first elements of 'with' are the 'poor' parts of the old answer
'without'
that are obviously unchanged.

The 'zipWith (++) rich using_cost' combines the previous 'rich' answers
without
'cost' with a new list that uses the 'cost' item.  This is:

using cost = (map add_cost with)

The using_cost list is made from taking the list of answers and prepending
the
'cost' item to all the solutions.

If this were applied to 'without' instead of 'with'...

using cost = (map add_cost without)

...then the definition of 'with' would not be recursive and would allow for
solutions that only order each menu item 0 or 1 times.

Since the definition of using_cost does apply the map to 'with' it can
all

The "n th" item in 'with' or 'without' has total price of "n", and after
add_cost it has a total price of "cost+n", and must be in the "(cost+n)th"
position in the answer 'with'.  This is achieve by the using_cost items
being
after the (poor ++) which means they have been shifted by (length poor)
positions which, by the definition of (splitN cost), is equal to 'cost'.
-------------- next part --------------
An HTML attachment was scrubbed...