1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
module AufgabeFFP3
where
import Prelude hiding (filter)
type Weight = Int
type Value = Int
type Item = (Weight, Value)
type Items = [Item]
type Load = [Item]
type Loads = [Load]
type LoadWghtVal = (Load, Weight, Value)
type MaxWeight = Weight
safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0
safeGet l i
| i < length l = l !! i
| otherwise = 0
toBin :: Integer -> [Integer] -- get binary representation of integer
toBin 0 = []
toBin i = [rem] ++ toBin quot
where ( quot, rem ) = quotRem i 2
hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set
hasBit num ith = (safeGet (toBin num) ith) == 1
getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l
getChoice l i = concat ( map (choose l) [0..(length l)-1] )
where
choose l pos
| hasBit (fromIntegral i) pos = [ l !! pos ]
| otherwise = []
generator:: Items -> Loads -- get all possible choices (2^n)
generator l = map ( getChoice l ) [1..num]
where num = (2^(length l)) - 1
transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items
transformer l = map trans l
trans :: Load -> LoadWghtVal -- worker of transformer
trans load = (load, weight, value)
where
weight = sum $ map fst load
value = sum $ map snd load
getWeight :: LoadWghtVal -> Weight
getWeight (_, w, _) = w
getVal :: LoadWghtVal -> Value
getVal (_, _, v) = v
filter :: MaxWeight -> [LoadWghtVal] -> [LoadWghtVal] -- drop those with too much weight
filter max l = [ x | x <- l, getWeight x <= max ]
selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val
selector l = [ x | x <- l, getVal x == max ]
where max = maximum $ map getVal l
selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val
selector1 = selector
selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight
selector2 l = [ x | x <- best, getWeight x == min ]
where
min = minimum $ map getWeight best
best = selector l
-- pascal's triangle from exercise 1
pd :: [[Integer]]
pd = [[1]] ++ (zipWith (\x y -> zipWith (+) ([0] ++ x) (y ++ [0])) pd pd)
-- naive
binom :: (Integer, Integer) -> Integer
binom (n, k)
| k == 0 || n == k = 1
| otherwise = binom (n-1, k-1) + binom (n-1, k)
-- stream using pascal
binomS :: (Integer, Integer) -> Integer
binomS (n, k) = pd !! fromInteger n !! fromInteger k
-- calc table
binomMemoTable :: [[Integer]]
binomMemoTable = [ [ binomM (n, k) | k <- [0..] ] | n <- [0..] ]
-- using memoisation
-- base case or recursion formula using lookup table
binomM :: (Integer, Integer) -> Integer
binomM (n, k)
| k == 0 || n == k = 1
| otherwise = get (n-1) (k-1) + get (n-1) (k)
where get n k = binomMemoTable !! fromInteger n !! fromInteger k
|
