揹包多種限制

Question

我有一個動態編程問題，我花了幾個小時研究無濟於事。

第一部分很簡單：你有一個揹包物品，你必須最大化這些物品的價值，同時保持它們低於一定的重量。

問題的第二部分是相同的，除了現在還有一個項目的限制。例如：

您可以放入包中的物品的最大值是多少，以便在重量和物品限制下最大化該值？

我不知道如何實現這個問題的第二部分，林尋找一個通用算法。

Answer 1

在沒有項目限制的動態編程solution中，您有2D矩陣，其中Y軸是項目索引，X軸是重量。然後，對於每個項目，重量對你選擇重量的最大

之間

• 值包括項目，如果項目重量< =重量的極限
• 值不包括項目

下面是例如在標準溶液的Python：

def knapsack(n, weight, values, weights): 
    dp = [[0] * (weight + 1) for _ in range(n + 1)] 

    for y in range(1, n + 1): 
     for x in range(weight + 1): 
      if weights[y - 1] <= x: 
       dp[y][x] = max(dp[y - 1][x], 
           dp[y - 1][x - weights[y - 1]] + values[y - 1]) 
      else: 
       dp[y][x] = dp[y - 1][x] 

    return dp[-1][-1] 

現在，當您添加項目限制時，您必須爲每個項目選擇最大值，值，使用的項目數讓我們從重量

• 值和n個項目，包括項目，如果項目重量< =重量限制
• 的重量和n項扣除項目

價值爲代表的項目的數量，你可以只添加第三維表示使用過的物品的數量之前使用的矩陣：

def knapsack2(n, weight, count, values, weights): 
    dp = [[[0] * (weight + 1) for _ in range(n + 1)] for _ in range(count + 1)] 
    for z in range(1, count + 1): 
     for y in range(1, n + 1): 
      for x in range(weight + 1): 
       if weights[y - 1] <= x: 
        dp[z][y][x] = max(dp[z][y - 1][x], 
             dp[z - 1][y - 1][x - weights[y - 1]] + values[y - 1]) 
       else: 
        dp[z][y][x] = dp[z][y - 1][x] 

    return dp[-1][-1][-1] 

簡單的演示：

w = 5 
k = 2 
values = [1, 2, 3, 2, 2] 
weights = [4, 5, 1, 1, 1] 
n = len(values) 

no_limit_fmt = 'Max value for weight limit {}, no item limit: {}' 
limit_fmt = 'Max value for weight limit {}, item limit {}: {}' 

print(no_limit_fmt.format(w, knapsack(n, w, values, weights))) 
print(limit_fmt.format(w, k, knapsack2(n, w, k, values, weights))) 

輸出：

Max value for weight limit 5, no item limit: 7 
Max value for weight limit 5, item limit 2: 5 

請注意，您可以優化例如關於內存消耗一點，因爲加入第i個項目，你只需要知道對於z解決方案的解決方案時 - 1項。你也可以檢查是否有可能將z物品放在重量限制之下，並且如果不能相應地減少物品限制。