[Haskell-cafe] xkcd #287 "NP-Complete"
Albert Y. C. Lai
trebla at vex.net
Tue Jul 10 15:26:01 EDT 2007
Marc A. Ziegert wrote:
> 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]]
You are right, I saw many solutions but they were all equivalent to just
those two. I did not avoid permutation-induced redundancy.
I was unsure how to eliminate that redundancy. After reading your
algorithm, I see it. Here is my algorithm modified.
import Data.List
import Control.Monad
-- exactly n v
-- items in v that sum to exactly n
-- returns list of solutions, each solution list of items
exactly :: (Real a) => a -> [a] -> [[a]]
exactly 0 v = return []
exactly n v = do
w@(c:w') <- tails v
guard (c <= n)
liftM (c :) (exactly (n - c) w)
-- for solutions that use items at most once,
-- change w to w'
play = exactly 1505 menu
menu = [215, 275, 335, 355, 420, 580]
More information about the Haskell-Cafe
mailing list