Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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<<uint(la))
sb := make([]Solution, 0, 1<<uint(lb))
var wg sync.WaitGroup
f := func(i []Item, sols *[]Solution) {
defer wg.Done()
for s := range NewSetChannel(i, -1) {
*sols = append(*sols, s)
}
}
// Fire these off in parallel
wg.Add(2)
go f(ia, &sa)
go f(ib, &sb)
wg.Wait()
sort.Sort(SolutionsByMass(sb))
var s Solution
for _, va := range sa {
for _, vb := range sb {
if va.Value+vb.Value > 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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment