There are no "recursive problems", only "recursive solutions"Originally Posted by newyork
For each recursive step you have a count of how many items you have in your bag, plus a second array of booleans which remembers which of the items are already in the bag, plus a total of their weight.
Then you have a loop of recursive calls, to try adding each of the unused items in the bag, one at a time, adjusting count and total for each call. For each call you update a global record of the best list of items, if the total is closer than the last remembered total.
Your base cases are that you've put more items in the bag than will fit, or when all items are in the bag and your bag is still not full.
It's O(n!) but it's the only way to guarantee that you find the optimal solution. Look up the knapsack problem!
