How to find elements in the Knapsack (twist- need to ALL ways of getting element)

Question

This is a classic Knapsack problem which I have solved using a Dynamic Programming approach.

Following on from here, I have a created a similar way to determine the type of elements that constitute the Knapsack. I need to find out ALL the ways the final answer can be gotten, not just one way. How can I do this?

Currently, I can only work backwards to find one way in which my items added to the max value. But in my input, I may have 2 or more ways in which items add to the max value. I want to know these 2 or more ways because then I have to choose an optimal set of items based on some criteria. How can I do this? Should I work on my DP matrix or my code below?

e.g. input

constraint:

maxWeight = 100

i.d./ value / weight

1/50/40

2/40/30

3/30/40

4/50/40

Output: based on constraint, I can have 1,2,3 or 2,3,4

Both add up to the same score and weight. How can I determine both sets?

Prelude:

I am determining if the item's time property in the arraylist falls within a certain limit. I have created a bool array (wasTaken) in my knapsack method where I put in the elements which could have been taken. Here I traverse my matrix to determine which element was taken, and then store the item's id for print (after sorting) later. int[][] sol below represents the matrix populated in a Dynamic Programming style from prior method. The i values represent items and the Weight values represent the weights being considered. This has been done in a manner similar to this link.

My current code:

public static void findElements(boolean[][] wasTaken, int maxWeight, ArrayList<Nodes> items, int[][] sol, int currentTime, int limit) {
        int K = maxWeight;
        int n = items.size();
        int count = 0;
        int[] forPrint = new int[n];
        for (int i = n-1; i>=0; i--) {
            if (wasTaken[i][K] == true && (currentTime - items.get(i).time <= limit)) {
                forPrint[i] = items.get(i).index;
                count++;
                K = K - items.get(i).height;

            }
        }
        Arrays.sort(forPrint);
        showResult(count, forPrint);
    }

Answer 1

For j from 1 to n, let p[j] be the profit of item j and let w[j] be the weight. For j from 0 to n and W from 0 up to the weight limit, let opt[j][W] be the maximum total profit choosing items from 1..j of total weight not greater than W. In computing opt, we have the recurrence

opt[j][W] = max(p[j] + opt[j - 1][W - w[j]],   opt[j - 1][W])    if j > 0 and W ≥ 0,
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^
                       item j chosen         item j not chosen
            0                                                    if j = 0 and W ≥ 0,
            -infinity (i.e., infeasible)                         if W < 0.

To enumerate all optimal solution, we work recursively and depth-first. Given j and W, if this is a base case, then yield the current set of chosen items (if W ≥ 0) or nothing at all (if W < 0). Otherwise, compare opt[j][W] with both arguments of the max. If it's equal to the first argument, then yield all solutions for j - 1 and W - w[j] with item j added to the set of chosen items. If opt[j][W] is equal to the second argument, then yield all solutions for j - 1 and W. We can yield multiple solutions because both arguments may be equal.