I am implementing a function with the following signature to solve the 0-1 knapsack problem in Haskell.
knapsack :: [Item] -> Capacity -> [Item]
Where the Item
and Capacity
files are defined as:
type Value = Int
type Weight = Int
type Capacity = Int
type Item = (Value, Weight)
I'd like to memoize it to have better performances. I tried to use Data.MemoCombinators but I can't get how to have it work.
Can you give me some hints?
I successfully used MemoTrie for tasks like this. Each type that you want to use as a memoization index must implement HasTrie
. In your case, you don't have to imlement anything, because the package already provides instances for the primitive data types as well as for pairs and lists.
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
If you're looking for performance optimization for operations on lists, I'd suggest to take a look at the strict iteration functions, for example Data.List.foldl'
:
foldl' :: (a -> b -> a) -> a -> [b] -> a
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With