Exploring the performance of different solutions to the 0-1 Knapsack Problem.

knapsack.go

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
}