[Haskell-cafe] xkcd #287 "NP-Complete"

[Marc A. Ziegert]

Am Dienstag, 10. Juli 2007 00:25 schrieb Albert Y. C. Lai:
> http://xkcd.com/c287.html

> It disappoints me that there is no solution if each item is used at most 
> once. However, do change the code to allow multiple uses, then there are 
> many solutions.

i see only two solutions.

let menu = [215, 275, 335, 355, 420, 580]
let run x menu = [[c]|c<-menu,c==x]++[c:cs|c<-menu,c<x,cs<-run (x-c) (dropWhile (/=c) menu)]
run 1505 menu

->
[[215,215,215,215,215,215,215],[215,355,355,580]]

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070710/28532147/attachment.bin