5

Haskellの0-1ナップサック問題を解決するために、次のシグネチャを持つ関数を実装しています。

knapsack :: [Item] -> Capacity -> [Item]

およびファイルは次のようItemにCapacity定義されます。

type Value = Int
type Weight = Int

type Capacity = Int

type Item = (Value, Weight)

より良いパフォーマンスを実現するために、メモ化したいと思います。Data.MemoCombinatorsを使用しようとしましたが、動作させる方法がわかりません。

ヒントを教えていただけますか？

4

2 に答える 2

6

私はこのようなタスクにMemoTrieをうまく使用しました。メモ化インデックスとして使用する各タイプは、を実装する必要がありますHasTrie。あなたの場合、パッケージはすでにプリミティブデータ型とペアおよびリストのインスタンスを提供しているため、何も実装する必要はありません。

import Data.MemoTrie

type Value = Int
type Weight = Int

type Capacity = Int

type Item = (Value, Weight)

knapsack :: [Item] -> Capacity -> [Item]
knapsack = memo2 knapsack'
  where
    knapsack' items capacity = ... -- your computation goes here
于 2012-12-29T21:25:44.800 に答える
2

リストでの操作のパフォーマンスの最適化を探している場合は、厳密な反復関数を確認することをお勧めします。次に例を示しData.List.foldl'ます。

foldl'::（a-> b-> a）-> a-> [b]-> a

于 2012-12-29T21:11:22.103 に答える