単価が異なるお菓子をどういう組み合わせで買えば目標の合計値になるか問題

先日、息子がとある算数の問題に挫折しているので覗いてみたら、確かにちょっと難しそうだった。「4種類の価格がまちまちのお菓子を任意個ずつ買ってキリがよい合計にする」という問題なんだけど、お菓子の単価と目標の合計値のみしか提示されていない ¹ 。当然、まるっきり当てずっぽうで正解が得られる感じではない。たぶん、答えが当ってるかどうかより、どういうアプローチで回答しようとしたかを見ることが問題の主旨であるような気がする。

で、これはまあ一種の切符問題なので、父さんならHaskellで解くなと思うだけ思ってそれきり忘れてたんですが、新千歳空港でお土産を買ってるときに思い出したので、成田までの機内で書きなぐってみました。抽象度が低くて残念な感じですが、当機はすでに着陸体制に入っています。（と思ったら成田が混雑してるので旋回しはじめた）

module Main where

import System.Environment

main :: IO ()
main = do
  -- 第一引数：目標の合計金額
  -- 残り：お菓子たちの単価
  x:xs <- fmap (map $ read) getArgs
  putStrLn $ show $ seek x (length xs) $ comb $ matrix xs

matrix :: [Int] -> [[(Int,Int)]]
matrix xs = map (\i -> map (\j -> (j,i)) [1..10]) xs

comb :: [[(Int, Int)]] -> [[(Int, Int)]]
comb [] = []
comb ([]:rest) = comb rest
comb ((x:xs):[]) = [[x]] ++ comb [xs]
comb ((x:xs):rest) = [(x:ys) | ys <- comb rest] ++ comb (xs:rest)

seek :: Int -> Int -> [[(Int, Int)]] -> [[(Int, Int)]]
seek target n = filter (totalIs target)
  where d (i,j) = i*j
        totalIs t xs = length xs == n && t == (sum $ map d xs)

問題の数字は覚えてないので、適当な合計金額と単価で実行例。

λ> :main "3000" "146" "172" "400" "500"
[[(4,146),(3,172),(1,400),(3,500)]]
λ> 

146円のお菓子が4個、172円のが3個、400円のが1個、500円のが3個で3000円になるらしいです。

---

1. 厳密には、それぞれの上限を10個とするとか、お菓子はなるべく高いものを多く買うとか、もうちょっと制限があった。 ↩