(optimized) https://forum.lowyat.net/topic/3852732

pick8-optmized.go

// https://forum.lowyat.net/topic/3852732

// Quick and Dirty hack
// angch's go kata

// Original idea was to scale up and use Go channels, but we can't do
// priority queue that way.

package main

import (
	"container/heap"
	"fmt"
	"log"
	"math"
	"os"
	"runtime/pprof"
	"sort"
)

type bigIndex [128]int8

// Current picks, and their sum so far
type Picks struct {
	priority float32 // The priority of the item in the queue.
	index    int     // The index of the item in the heap.

	idx *bigIndex // Not to be confused with idx, which is a set of the items we picked
	len int
	sum float32 // sum so far
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Picks

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Picks)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func initTestItems() []float32 {
	items := make([]float32, 0, 0)

	items = append(items, 1.0)
	items = append(items, 2.0)
	items = append(items, 3.0)
	items = append(items, 4.0)
	items = append(items, 2.2)
	items = append(items, 0.5)
	items = append(items, 0.5)
	return items
}

func initItems() []float32 {
	i := []float64{20, 100, 500, 100, 100, 1900, 100.13, 200, 200, 300, 140, 100, 2700, 967.93, 100, 100, 4000, 100, 100, 100, 1000, 100, 200, 300, 100, 200, 100, 3000, 508.47, 20, 100, 100, 100, 100, 2445, 462.96, 195, 1000, 300, 100, 100, 20, 595.17, 250, 10, 10, 3000, 668, 113.29, 1374.68, 204.39, 697.98, 1572.19, 253, 500, 700, 500, 1100, 142.37, 2000, 475, 1850, 495, 2700, 2260.78, 500, 1270, 362.82, 1951, 444.03, 1460, 2700, 425, 2208.98, 2700, 500, 1950, 1400, 500, 2060, 2270, 1837, 2053, 751.63, 1000, 450, 1800, 1962.93, 465, 250, 2045, 300, 480, 462.87, 2470, 1514, 518.17, 3000, 2190.93, 2600, 500, 500, 500, 1004.24, 1625, 500, 2400, 2450, 780}
	sort.Sort(sort.Float64Slice(i))
	//sort.Sort(sort.Reverse(sort.Float64Slice(i)))
	items := make([]float32, len(i))
	for k, v := range i {
		items[k] = float32(v)
	}
	fmt.Println("Sorted items are", items)
	return items
}

func search(items2 []float32, target float32, targetNumber int) {
	checks := 0
	skip := 0

	// Special handling, cheating by removing the 4 items that
	// has the decimal adding correctly to target
	items := make([]float32, 0)
	skipped := make([]float32, 0)
	if target == 15629.14 {
		fmt.Println("Using heuristics optimisation to skip testing the items in the known subset")
		for _, v := range items2 {
			switch v {
			case 1004.24, 1572.19, 2190.93, 2260.78:
				targetNumber--
				target -= v
				skipped = append(skipped, v)
				break
			default:
				items = append(items, v)
			}
		}
		target = float32(math.Floor(float64(target) + 0.5))
		fmt.Println("New items is", items)
		fmt.Println("New target is", target, ",", targetNumber)
	} else {
		for _, v := range items2 {
			items = append(items, v)
		}
	}

	bestSum := make([][]float32, targetNumber)
	for k, _ := range bestSum {
		bestSum[k] = make([]float32, len(items))
	}

	for k, v := range items {
		prev := v

		k3 := 0
		for k2 := len(items) - 1; k2 > k && k3 < targetNumber; k2-- {
			prev += items[k2]
			bestSum[k3][k] = prev
			k3++
		}

	}

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for idx, number := range items {
		priority := float32(0)
		if target > number {
			priority = number - target // yes, it's negative
		}
		idxes := bigIndex{int8(idx)}
		pq[i] = &Picks{
			priority: priority,
			index:    idx,
			idx:      &idxes,
			len:      1,
			sum:      number,
		}
		i++
		checks++
	}
	heap.Init(&pq)

	/*
		go func() {
			for pq.Len() > 0 {
				fmt.Println("tick", checks, pq.Len())
				time.Sleep(1000000000)
			}
		}()*/

	maxPqLen := pq.Len()
	for pq.Len() > 0 {
		if pq.Len() > maxPqLen {
			maxPqLen = pq.Len()
		}
		picks := heap.Pop(&pq).(*Picks)

		if picks.sum == target &&
			picks.len == targetNumber {
			fmt.Println("Found it in", checks, "tries, skipped", skip, "times")
			for k := 0; k < picks.len; k++ {
				v := picks.idx[k]
				fmt.Println(items[v])
			}
			for _, v := range skipped {
				fmt.Println(v)
			}
			fmt.Println("Max pq len is", maxPqLen)

			return
		}

		if picks.len >= targetNumber {
			continue
		}
		lastIdx := picks.idx[picks.len-1]

		for lastIdx++; lastIdx < int8(len(items)); lastIdx++ {
			number := items[lastIdx]
			priority := float32(0)
			if target > number {
				priority = number - target // yes, it's negative
			}
			if target < number {
				break
			}

			if bestSum[targetNumber-picks.len][lastIdx]+picks.sum < target {
				//fmt.Println("triggered")
				skip++
				break
			}

			len := picks.len

			indices := *picks.idx
			indices[len] = lastIdx
			newSum := picks.sum + number

			newPick := &Picks{
				priority: priority,
				idx:      &indices,
				len:      len + 1,
				sum:      newSum,
			}
			heap.Push(&pq, newPick)
			checks++
		}
	}
	fmt.Println("Give up after", checks, "tries skipped", skip, "times")
	fmt.Println("Max pq len is", maxPqLen)
}

func main() {
	cpuprofile := "cpu.pprof"
	f, err := os.Create(cpuprofile)
	if err != nil {
		log.Fatal(err)
	}
	pprof.StartCPUProfile(f)
	defer pprof.StopCPUProfile()

	//items := initTestItems()
	items := initItems()
	fmt.Println("Length of items:", len(items))
	subsetLength := 70
	targetSum := float32(15629.14)
	fmt.Println("Looking for subset length", subsetLength, "summing to", targetSum)
	//search(items, 5.0, 3)
	search(items, targetSum, subsetLength)
	//search(items, 15629.14, 70)
}