Solution to http://programmingpraxis.com/2012/05/15/streaming-knapsack/

Streaming_Knapsack.go

package main

import (
	"fmt"
	"math/rand"
)

/*
A famous problem of computer science is the knapsack problem, in which you are to find a combination of items from a population that sums to a given target, 
often with some kind of constraint such as maximizing the value of the items. In today’s problem we want to find the first possible combination 
of k integers from a stream of positive integers that sum to n. For instance, given the input stream 4, 8, 9, 2, 10, 2, 17, 2, 12, 4, 5, …, 
we want to find the knapsack containing 4, 2, 10, 2, 2 immediately after reading the third 2, without reading the 12, 4, 5 that follow it.

Your task is to write a program that takes parameters k and n and an input stream and returns the first possible knapsack. 
When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

*/

func PackKnapsack(istream <-chan int, r int, sum int) []int {
	vals := make([]int, 0)
	for nextInt := range istream {
		vals = append(vals, nextInt)
		fmt.Println(vals)
		for poses := range CombinationGenerator(len(vals)-1, r-1) {
			poses = append(poses, len(vals)-1)
			if fitsKnapsack(poses, vals, sum) {
				return poses
			}
		}
	}
	return nil
}

func fitsKnapsack(poses []int, vals []int, n int) bool {
	fmt.Println("trying ", poses)
	sum := 0
	for _, v := range poses {
		sum += vals[v]
	}
	fmt.Println("sum == ", sum)
	return sum == n
}

func Copy(x []int) []int {
	y := make([]int, len(x))
	copy(y, x)
	return y
}

func CombinationGenerator(n int, r int) <-chan []int {
	out := make(chan []int)
	go func() {
		if n < r {
			fmt.Printf( "%d > %d\n", r, n)
			close(out)
			return
		}
		//output each choice of n from r

		//setup
		result := make([]int, r)
		for i := 0; i < r; i++ {
			result[i] = i
		}

		done := false
		for !done {
			out <- Copy(result)
			//increment
			incPos := r - 1
			didIncrement := false
			for !didIncrement && incPos >= 0 {
				if result[incPos] < (n - r + incPos ) {
					result[incPos]++
					for j := incPos+1; j< r;j++ {
						result[j] = result[incPos]+(j - incPos) 
					}
					didIncrement = true
				} else {
					incPos --
				}
			}
			//if can't increment, done
			if !didIncrement {
				done = true
			}
		}
		//done, close the channel
		close(out)
	}()
	return out
}

func nextInt() <-chan int {
	out := make(chan int)
	go func() {
		for {
			out <- rand.Int() % 5 + 1
		}
	}()
	return out
}

func main() {
	rand.Seed(10)
	fmt.Println(PackKnapsack(nextInt(), 6, 20))
}