如何獲得從揹包DP矩陣

我對一個揹包問題DP解決方案工作的所有解決方案。有一個項目的列表與他們的重量和價值，我需要找到最大總值小於某個預定義權重的項目。沒什麼特別的，只是0-1 knapsack。如何獲得從揹包DP矩陣

我用DP來生成矩陣：

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

其中數據項的元組(name, weight, value)的列表。現在有一個DP矩陣，他的最大可能值是右下位置的數字。我也可以回溯矩陣以找到提供最佳解決方案的項目列表。

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

太好了，現在我可以得到結果：

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)

，將看到：[('fifth', 1, 2), ('third', 2, 5), ('second', 3, 8), ('first', 1, 1)]。

問題是這不是一個獨特的解決方案。取而代之的是'first'元素，我可以採取'forth'元素（這絕對是一樣的，但有時的解決方案可以是不同的）。我想弄清楚如何得到所有的解決方案，而不是一個。我意識到這將需要更多時間，但我確定。

來源

2015-05-31 Salvador Dali

你可以計算原始DP矩陣像往常一樣（即，使用DP），但是要找到你需要遞歸，你通過從最終狀態矩陣出差回來所有的最優解。這是因爲在矩陣中的任何給定的狀態（I，J）至少有一個最佳的前驅狀態，但它可能有兩個：它可能是通過選擇到最大值的狀態（I，J）可以實現兩種添加項目i爲狀態（I-1，JW（I）），則最優解或通過留下項目i出來，只是保持對於第（i-1，j）的最優解。發生這種情況的確切時間這兩種選擇產生相等的總值，即，當

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

其中w（i）和V（I）是重量和目標i的值，分別。無論何時您檢測到這種分支，都需要關注每個分支。

注意，有可能是一個非常大的數量的最佳解決方案：例如，考慮當所有項目都重。在這種情況下，所有（n個選擇w）解決方案是最優的。

來源

2015-05-31 18:06:14

如何獲得從揹包DP矩陣

回答

相關問題