如何有效率地確定最佳背包方案中包含的物品？

確定最佳背包解決方案中的元素

給定的背包演算法有效地計算裝箱問題的最優值。然而，目前的任務是確定構成此最佳解決方案的元素。

1.追蹤選擇：

計算出 dp 矩陣中的最優值後，我們可以回溯以確定所選元素。

dp_copy = dp;  // Copy the dp matrix for backtracking

int weight_idx = W;
int item_idx = n;

while (weight_idx > 0 && item_idx > 0):
    if dp_copy[weight_idx][item_idx] != dp_copy[weight_idx - items[item_idx - 1].getWeight()][item_idx - 1]:
        // Element 'item_idx' is included in the optimal solution
        weight_idx -= items[item_idx - 1].getWeight()
        item_idx -= 1

2.偽代碼解釋：

• 我們以相反的順序從最後一個單元格到第一個單元格迭代 dp 矩陣。
• 我們檢查目前單元格與矩陣中上方和左側的單元格等於對應項目的權重。
• 如果是，則與該儲存格值關聯的項目包含在解決方案中。
• 我們相應地調整權重索引和項目索引以進一步回溯。

3.複雜度：

這種回溯方法需要O(W * n) 時間複雜度，其中W 是袋子容量，n 是物品數量。它遍歷矩陣中的每個單元一次並執行恆定時間搜尋操作。

以上是如何有效率地確定最佳背包方案中包含的物品？的詳細內容。更多資訊請關注PHP中文網其他相關文章！