問題内容

13kgの容量のナップザックに

の商品を詰めて, 価格を最大化します

この問題では, 同じ商品を複数個詰めても良いことになっています.

私が電卓だけ使って解いたらB,B,C,Dになりました.

しかしこれを学内システムに入力したら間違いになりました.

じゃあWolframで検算してみようと思い, KnapsackSolve—Wolfram言語ドキュメントを見て入力してみましたが, 何故かサンプルの入力すら通りません. 諦めました.

Maximaは暫く使ってないですし, 0|1の場合のナップザック問題ぐらいしか解いたことがありません. 複数個取っていい場合はどうやって書くんでしょうね.

なのでHaskellで自分で書くことにしました.

Haskellで解く方法

まず, 商品の選択量を入力します. 普通ナップザック問題というと詰めるか詰めないかなので0か1なのですが, 今回は複数個詰められるということなので重さ1の商品が最大個詰められる13まで選択できるようにします.

Prelude> let r = [0 .. 13]

商品の価格を入力.

Prelude> let [av, bv, cv, dv, ev] = [450, 570, 225, 110, 670]

商品の重さを入力.

Prelude> let [ac, bc, cc, dc, ec] = [4, 5, 2, 1, 6]

必要なものをimportする.

Prelude> import Data.Foldable
Prelude Data.Foldable> import Data.Ord

リスト内包表記で愚直に書きます. ちょっと愚直すぎると思います. もうちょっとエレガントな書き方はないでしょうか…

Prelude Data.Foldable Data.Ord> maximumBy (comparing fst) [(as * av + bs * bv + cs * cv + ds * dv + es * ev, (as, bs, cs, ds, es)) | as <- r, bs <- r, cs <- r, ds <- r, es <- r, as * ac + bs * bc + cs * cc + ds * dc + es * ec <= 13]
(1475,(0,2,1,1,0))

あれっ勘で解いたのと同じになってしまいました. 私の解き方が間違っていると思ったのですが…

寝坊して行けなかったので即座に聞くことが出来ません. 自業自得なのですが.

これを自力で解くことは諦めて, メールで質問することにします.

こういうのを書いていると, IHaskellが便利なのかな? と思えてきますがJSONなどの構造体を扱ってないですし特に便利でもないか.

メールで質問したらカンマ区切りはミス表記でカンマで区切らないのが正解でした. わざわざプログラム組む必要はなかったですね. 数分なので問題ないですが.