Is this problem a knapsack problem?

Is there a way to print out all solutions to the 0-1 Knapsack problem using dynamic programming in O(nC) time?

• Currently there exists a way to print out one possible solution.  However I want print out all solutions in O(nC) time, where n is the number of items and C is the total capacity of the knapsack. If there is, can you also describe the algorithm in pseudocode. Psuedocode for printing out 1 solution to the knapsack problem[1]. [1]-http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

• Answer:

  Typically, when you are doing the table filling with DP, you keep a single best parent pointer to a parent that got you to the current state.  Replace that single pointer with a list of pointers to all parent states that could have gotten you to the current state. To print the old single answer, you used to walk single optimal parent pointers from each step recover the full solution.  Instead now you recursively branch any time you have a choice and collect all of the optimal solutions. Note that even if finding a single solution takes O(nC), there can be exponentially many optimal solutions, and printing out each one will take O(n).  So you'll potentially have to spend an exponential amount of time just to write the answers.  On the other hand, if you are willing to allow for an output sensitive algorithm, there is a way to print out all K optimal solutions in time O(nC + nK).