Printing out result in 0/1 KnapSack (Recursive Brute Force)

Question

public static int KnapSack(int capacity, Item[] items, int numItems) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1);
    else {
        int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1);
        int left = KnapSack(capacity, items, numItems-1);
        return Math.max(took, left);
    }     
}  

So I have a working 0/1 recursive brute force algorithm working for the KnapSack problem. I was wondering of what would be an approach to print out the working solution (i.e the items collected into the knapsack from the set of items). I've tried a number of things such as adding into a list and trying to keep track of what things I have added, but none of worked out either do to implementation or design problem. So I came here for some help, thanks!

Answer 1

To track the items taken, try something like:

public static int KnapSack(int capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1, taken);
    else {
        final int preTookSize = taken.size();
        final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);

        final int preLeftSize = taken.size();
        final int left = KnapSack(capacity, items, numItems-1, taken);

        if (took > left) {
            if (taken.size() > preLeftSize)
                taken.removeRange(preLeftSize, taken.size());
            taken.add(Integer.valueOf(numItems - 1));
            return took;
        }
        else {
            if (preLeftSize > preTookSize)
                taken.removeRange(preTookSize, preLeftSize);
            return left;
        }
    }     
}

This may not be the most efficient, but I think it should work.

(For efficiency you might try pre-allocating the taken ArrayList to be "big enough" such that no allocations need to happen during the recursive looping.)