ナップザック問題をHaskellで解いてみる

Python ナップザック問題を分枝限定法( branch and bound )で解くを読んで、問題は理解できたけど、アルゴリズムはさっぱりでした。
でも、Haskellならきっと答えを教えてくれる、とやってみたのでメモ。

--問題(元記事より引用)
2*x1 + 3*x2 + 5*x3 + 6*x4 <= 9
xi = 0 or 1 (i = 1, 2, 3, 4)

上記条件の下で
4*x1 + 5*x2 + 12*x3 + 14*x4
を最大にする( x1, x2, x3, x4 )を分枝限定法を用いて求めよ。

分枝限定法っていうのは分からなかったので、申し訳ありませんがスルーさせてもらって、

• 容量条件を満たす個数のリストと、そのときの価値とのタプルのリストを作り、
• その中から、最大の価値を持つ要素のリストを求める

てな感じで。総当たりです。
リスト内包表記ってのをなるべく使ってみました。

maxElem cs c ps = [ x | x <- ys
                    , snd x == (maximum $ map snd ys ) 
                	]
    where
        ys = availables cs c ps

availables cs c ps = [ (xs, sumZipProd xs ps ) |  xs <- ys
                                            , (sumZipProd xs cs ) <= c
                    ]
    where
        ys = [ [y0, y1, y2, y3] | y0 <- zs
                                , y1 <- zs
                                , y2 <- zs
                                , y3 <- zs
            ]
        zs = [0, 1]
        sumZipProd xs ys = sum $ zipWith (*) xs ys

main = print $ maxElem  [2, 3, 5, 6] 9 [4, 5, 12, 14]

--実行結果
[([0,1,0,1],19)]

ベタな感じですが、答えは出ました。

• リストの扱い方
• 賢いアルゴリズム

について、もっと良い方法があれば教えていただけると有り難いです。