CS nerd friday problem

[drummaniac83]

I came across what is probably a common problem and thought some of the super nerds here might have fun with this question:

take a sorted (increasing) array of arbitrary values.....ie {1,2,3,5,8,12,16}

now for any desired value, return a subset array of the values that SUM to the desired value. Elements can only be used once, obviously there might be multiple solutions. Like for the above array 8 would have 2 solutions: {3,5} or {8}.

My particular problem was not as arbitrary, so I was able to use a combination of thresholding and number to boolean array to determine the value.

My instinct tells me nested loops would work but messy, possibly some form of recursion might be better, or is there a way to solve this with a linear system.

Any thoughts?

[nathand · Accepted solution]

This is the classic CS Knapsack Problem.

I imagine a solution like this: Put the next element of the array into the "sack", along with the index of that element. Then you have three options:

- The sum in the sack is less than the goal. If so, increment the array index, and repeat.

- The sum in the sack is equal to the goal. Add to the list of solutions, empty the sack, add one to the index of the first item that was in the sack, and repeat.

- The sum is greater than the goal. Take out the most-recently added item, increment its index, and repeat. If at the end of the list, take out the next-most-recently-added item, increment its index, and repeat.

If I have time later or over the weekend maybe I'll post real code.

[drummaniac83]

Beautiful.  Just the kind of background I was hoping to get.  I figured this was something that had been studied ad nauseum.  I would be interested in seeing a solution, but the wikipedia is enough for me just to know for the future.

Thanks so much!