Knapsack問題

Haskellでナップザック問題。

import Data.List

type Value = Int
type Weight = Int

type Product = (Value,Weight)

main = do
 capacity <- getLine
 n <- getLine
 cs <- getContents
 print.knapsack (read capacity).makeTuple (read n) $ cs

makeTuple n
 = map ((\[a,b]->(a,b)).map read.words).take n.lines

knapsack :: Int -> [Product] -> Int
knapsack c = foldl max 0. map (fst.foldl toBag (0,c)).permutations

toBag a b | snd a >= snd b =(fst a + fst b,snd a - snd b)
          | otherwise      = a

permutationsがあるので楽ですね。
ただ、上のコードでは、ナップザック容量を越えた後も処理しつづけるので無駄が生じています。
takeWhileとかMaybeを使って途中で打ちきると良さそう。

あと、一つ前の記事で、
二つ目に解いたcodeforcesの問題がありましたが、
foldl使って、1/2程度の量で書けたので載せておく。

main = getLine >>= putStrLn.answer

answer :: String -> String
answer ('-':cs) = "($"++ format cs ++ ")"
answer str      =  "$"++ format str

format str
 = let intPart = takeWhile (/='.') str
       floatPart = drop (1+length intPart) $ str
   in  formatI intPart  ++ formatF floatPart

formatI str = fst$foldl f ([],3-mod (length str) 3) str
 where
  f (str,0) c = (str++","++[c] , 1)
  f (str,m) c = (str++[c],mod (m+1) 3)

formatF str = '.':(take 2 $ take 2 str ++ repeat '0')