python - How to derive all solutions from knapsack DP matrix -

i working on dp solution knapsack problem. having list of items weights , value, need find items maximum total value less predefined weight. nothing special, 0-1 knapsack.

i use dp generate matrix:

def getknapsacktable(items, limit):     matrix = [[0 w in range(limit + 1)] j in xrange(len(items) + 1)]     j in xrange(1, len(items) + 1):         item, wt, val = items[j-1]         w in xrange(1, limit + 1):             if wt > w:                 matrix[j][w] = matrix[j-1][w]             else:                 matrix[j][w] = max(matrix[j-1][w], matrix[j-1][w-wt] + val)      return matrix 

where items list of tuples (name, weight, value). having dp matrix, maximum possible value number in right down position. can backtrack matrix find list of items gives best solution.

def getitems(matrix, items):     result = []     i, j = len(matrix) - 1, len(matrix[0]) - 1     in range(i, 0, -1):         if matrix[i][j] != matrix[i-1][j]:             item, weight, value = items[i - 1]             result.append(items[i - 1])             j -= weight      return result 

great, can results:

items = [('first', 1, 1), ('second', 3, 8), ('third', 2, 5), ('forth', 1, 1), ('fifth', 1, 2), ('sixth', 5, 9)] matrix = getknapsacktable(items, 7) print getitems(matrix, items) 

and see: [('fifth', 1, 2), ('third', 2, 5), ('second', 3, 8), ('first', 1, 1)].

---

the problem not unique solution. instead of 'first' element, can take 'forth' element (which absolutely same, solutions can different). trying figure out how solutions instead of one. realize take more time, ok that.

you can compute original dp matrix usual (i.e., using dp), find optimal solutions need recurse travel through matrix final state. that's because given state (i, j) in matrix has @ least 1 optimal predecessor state, it might have two: might maximum value state (i, j) can achieved either choosing add item optimal solution state (i-1, j-w(i)), or leaving item out , keeping optimal solution (i-1, j). occurs when these 2 choices yield equal total values, i.e., when

matrix[i-1][j] == matrix[i-1][j-w(i)]+v(i), 

where w(i) , v(i) weight , value of object i, respectively. whenever detect such branching, need follow each branch.

note there extremely large number of optimal solutions: e.g., consider case when items have weight 1. in case, (n choose w) solutions optimal.