Instantly share code, notes, and snippets.

# ibd1279/knapsack.go Created Aug 2, 2016

Exploring the performance of different solutions to the 0-1 Knapsack Problem.
 package main import ( "log" "sort" "sync" "time" ) type Item struct { Name string Mass, Value int } var ITEMS = []Item{ Item{"map", 9, 150}, Item{"compass", 13, 35}, Item{"water", 153, 200}, Item{"sandwich", 50, 160}, Item{"glucose", 15, 60}, Item{"tin", 68, 45}, Item{"banana", 27, 60}, Item{"apple", 39, 40}, Item{"cheese", 23, 30}, Item{"beer", 52, 10}, Item{"suntan cream", 11, 70}, Item{"camera", 32, 30}, Item{"T-shirt", 24, 15}, Item{"trousers", 48, 10}, Item{"umbrella", 73, 40}, Item{"waterproof trousers", 42, 70}, Item{"waterproof overclothes", 43, 75}, Item{"note-case", 22, 80}, Item{"sunglasses", 7, 20}, Item{"towel", 18, 12}, Item{"socks", 4, 50}, Item{"book", 30, 10}, Item{"notebook", 90, 1}, Item{"tent", 200, 150}, } type ByMass []Item func (self ByMass) Len() int { return len(self) } func (self ByMass) Less(i, j int) bool { return self[i].Mass < self[j].Mass } func (self ByMass) Swap(i, j int) { tmp := self[i] self[i] = self[j] self[j] = tmp } type ByName []Item func (self ByName) Len() int { return len(self) } func (self ByName) Less(i, j int) bool { return self[i].Name < self[j].Name } func (self ByName) Swap(i, j int) { tmp := self[i] self[i] = self[j] self[j] = tmp } type Solution struct { Items []Item Mass, Value int } const MAX_WEIGHT = 500 func main() { // DP. s := DynamicProgramming(ITEMS) sort.Sort(ByName(s.Items)) log.Printf("V = %v\tW = %v\tI = %v", s.Value, s.Mass, s.Items) // Meet in the Middle s = MeetInTheMiddle(ITEMS) sort.Sort(ByName(s.Items)) log.Printf("V = %v\tW = %v\tI = %v", s.Value, s.Mass, s.Items) // BTree Search s = BTreeSearch(ITEMS) sort.Sort(ByName(s.Items)) log.Printf("V = %v\tW = %v\tI = %v", s.Value, s.Mass, s.Items) // Brute Force Search s = BruteForce(ITEMS) sort.Sort(ByName(s.Items)) log.Printf("V = %v\tW = %v\tI = %v", s.Value, s.Mass, s.Items) } // BTree Search Implementation func BTreeSearch(items []Item) Solution { defer LogElapsedTime(time.Now(), "BTreeSearch") // Solve the problem. solution := Solution{Items: []Item{}, Value: 0, Mass: 0} for s := range NewSetChannel(items, MAX_WEIGHT) { if solution.Value < s.Value { solution = s } } return solution } // Dynamic Programming Implementation func DynamicProgramming(inputs []Item) Solution { defer LogElapsedTime(time.Now(), "DynamicProgramming") l := len(inputs) w := MAX_WEIGHT m := make([]int, (l+1)*w) for i := 1; i <= l; i++ { for j := 0; j < w; j++ { if inputs[i-1].Mass > j { m[i*w+j] = m[(i-1)*w+j] } else { up := m[(i-1)*w+j] link := m[(i-1)*w+(j-inputs[i-1].Mass)] value := inputs[i-1].Value if up > link+value { m[i*w+j] = up } else { m[i*w+j] = link + value } } } } // Create the PackList pl := make([]Item, 0, l) ms := 0 for i, j := l, w-1; i > 0 && j >= 0; i-- { if (i == 0 && m[i*w+j] > 0) || m[i*w+j] != m[(i-1)*w+j] { pl = append(pl, inputs[i-1]) ms += inputs[i-1].Mass j -= inputs[i-1].Mass } } v := m[l*w-1] return Solution{Value: v, Mass: ms, Items: pl} } // Meet in the Middle Implementation type SolutionsByMass []Solution func (self SolutionsByMass) Len() int { return len(self) } func (self SolutionsByMass) Less(i, j int) bool { return self[i].Mass < self[j].Mass } func (self SolutionsByMass) Swap(i, j int) { tmp := self[i] self[i] = self[j] self[j] = tmp } func MeetInTheMiddle(inputs []Item) Solution { defer LogElapsedTime(time.Now(), "MeetInTheMiddle") la := len(inputs) / 2 ia := inputs[:la] ib := inputs[la:] lb := len(ib) sa := make([]Solution, 0, 1< s.Value && va.Mass+vb.Mass < MAX_WEIGHT { s = va s.Items = append(s.Items, vb.Items...) s.Value += vb.Value s.Mass += vb.Mass } if vb.Mass+va.Mass > MAX_WEIGHT { break } } } return s } // Brute Force Implementation func BruteForce(items []Item) (ret Solution) { defer LogElapsedTime(time.Now(), "BruteForce") // Solve the problem. for s := range NewSetChannel(items, -1) { if s.Mass < MAX_WEIGHT && s.Value > ret.Value { ret = s } } return } // Utility Functions func LogElapsedTime(start time.Time, name string) { elapsed := time.Since(start) log.Printf("%s took %v", name, elapsed) } func NewSetChannel(inputs []Item, maxWeight int) (ret chan Solution) { // Prealloc what we think we will need. pow := 1 << uint(len(inputs)) prefixes := make([][]Item, 1, pow) context := make([][]Item, 1, pow) context[0] = inputs // Create the coroutine to populate the channel. ret = make(chan Solution, 5) go func() { defer close(ret) for i := 0; i < len(prefixes); i++ { prefix := prefixes[i] pieces := context[i] s := Solution{Items: prefix, Value: 0.0, Mass: 0.0} for _, v := range s.Items { s.Value += v.Value s.Mass += v.Mass } if maxWeight == -1 || s.Mass < maxWeight { for k, v := range pieces { // Create a copy of the prefix since append is destructive. subPrefix := make([]Item, len(prefix), len(prefix)+1) copy(subPrefix, prefix) subPrefix = append(subPrefix, v) // Fake the recursion prefixes = append(prefixes, subPrefix) context = append(context, pieces[k+1:]) } ret <- s } prefixes[i] = nil context[i] = nil } }() return }