A Brute force solution to the knapsack problem

main.go

package main

import (
	"flag"
	"fmt"
	"io/ioutil"
	"math"
	"strconv"
	"strings"
	"sync"
	"time"
)

var (
	wg       sync.WaitGroup
)

func createSolutions(nums []float64, wanted float64) chan int {
	channel := make(chan int, 1000)

	go func() {
		for {
			select {
			case value := <-channel:
				var values []float64
				powTwo := 1
				var indexes []int
				var total float64
				for k := 0; k < len(nums); k++ {
					if powTwo&value == 0 {
						powTwo *= 2
						continue
					}
					powTwo *= 2
					indexes = append(indexes, k)
					values = append(values, nums[k])
					total += nums[k]
				}
				fmt.Printf("Found - %v --- %v == %v (%.4f%%)\n", indexes, values, total, 100*total/wanted)
			}
		}
	}()

	return channel
}

func calculate(nums []float64, wanted, maxError float64, numCoresToUse, coreNumber int, solutions chan<- int) {
	defer wg.Done()
	combs := math.Pow(2, float64(len(nums)))
	size := math.Ceil(combs / float64(numCoresToUse))
	start := int(size) * coreNumber
	top := int(math.Min(combs, float64(start)+size))

	for i := start; i <= top; i++ {
		var total float64
		powTwo := 1
		for k := 0; k < len(nums); k++ {
			if powTwo&i == 0 {
				powTwo *= 2
				continue
			}
			powTwo *= 2
			total += nums[k]
		}

		if math.Abs(total-wanted) < maxError {
			solutions <- i
		}
	}
}

func main() {

	inputFile := flag.String("input", "input.txt", "The input file.")
	cores := flag.Int("cores", 4, "Cores to use")
	tolerance := flag.Float64("tolerance", 0.01, "sum has to be this close to wanted to be accepted")
	flag.Parse()

	maxError := *tolerance

	contents, err := ioutil.ReadFile(*inputFile)
	if err != nil {
		fmt.Printf("Unable to read file: %v\n", err)
		return
	}

	var target float64
	var nums []float64

	for idx, val := range strings.Split(string(contents), "\n") {
		if val == "" {
			continue
		}

		trimmedVal, err := strconv.ParseFloat(strings.TrimSpace(val), 64)
		if err != nil {
			fmt.Printf("Unable to read line %v: '%s' --- Got error: %v\n", idx, val, err)
			return
		}
		if idx == 0 {
			target = trimmedVal
		} else {
			nums = append(nums, trimmedVal)
		}
	}

	fmt.Printf("Attempting to find %v within an error of %v using %v values. Using %v cores.\n",
		target, maxError, len(nums), *cores)

	start := time.Now()
	wg.Add(*cores)

	for i := 0; i < *cores; i++ {
		go calculate(nums, target, maxError, *cores, i, createSolutions(nums, target))
	}

	wg.Wait()
	totalTime := time.Now().Sub(start)
	<-time.After(100*time.Millisecond)
	fmt.Println("Done:", totalTime)
}