CODEWITHSUNDEEP
pythonalgorithmdynamic-programmingknapsack-problem
Salvador Dali
Salvador Dali

Reputation: 222581

How to derive all solutions from knapsack DP matrix

I am working on DP solution for a knapsack problem. Having a list of items with their weights and value, I need to find the items with the maximum total value less then some predefined weight. Nothing special, just 0-1 knapsack.

I use DP to generate a matrix:

def getKnapsackTable(items, limit):
    matrix = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
    for j in xrange(1, len(items) + 1):
        item, wt, val = items[j-1]
        for 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 are a list of tuples (name, weight, value). Now having a DP matrix, he maximum possible value is the number in the right down position. I can also backtrack the matrix to find the list of items that gives the best solution.

def getItems(matrix, items):
    result = []
    I, j = len(matrix) - 1, len(matrix[0]) - 1
    for i 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, now I can get the 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 will see: [('fifth', 1, 2), ('third', 2, 5), ('second', 3, 8), ('first', 1, 1)].

The problem is that this is not a unique solution. Instead of the 'first' element, I can take the 'forth' element (which is absolutely the same, but sometimes the solutions can be different). I am trying to figure out how to get all the solutions instead of just one. I realize that it will take more time, but I am ok with that.

Upvotes: 5

Views: 2097

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

You can compute the original DP matrix as usual (i.e., using DP), but to find all optimal solutions you need to recurse as you travel back through the matrix from the final state. That's because any given state (i, j) in your matrix has at least one optimal predecessor state, but it might have two: it might be that the maximum value for state (i, j) can be achieved either by choosing to add item i to the optimal solution for state (i-1, j-w(i)), or by leaving item i out and just keeping the optimal solution for (i-1, j). This occurs exactly when these two choices yield equal total values, i.e., when

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

where w(i) and v(i) are the weight and value of object i, respectively. Whenever you detect such a branching, you need to follow each branch.

Note that there could be an extremely large number of optimal solutions: e.g., consider the case when all items have weight 1. In this case, all (n choose w) solutions are optimal.

Upvotes: 2

Related Questions