保持動態編程步驟的跟蹤

Question

我在教自己的基本編程原則，而且我被困在動態編程問題上。讓我們看看臭名昭着的揹包問題：

給定一組項目，每個項目都有一個權重和一個值，確定要包括在一個集合中的每個項目的計數，以便總權重小於或等於給定限制總價值儘可能大。我們將權重限制設置爲10，並且給出兩個列表：權重= [2,4,7]和值= [8,4,9]（我剛剛完成了這些）。我可以編寫代碼給出約束條件下的最大值 - 這不是問題。但是如果我想知道我實際上最終使用了什麼值，那麼呢？不是總價值 - 個人價值。因此，對於這個例子，最大值將是權重爲2和7的對象，總值爲8 + 9 = 17。儘管如此，我不想讓我的答案閱讀「17」 - 我想要輸出一個列表如：（8,9）。這個問題可能很容易，但我正在處理的問題使用的列表要大得多，並且有重複的數字（例如，多個對象的值爲8）。

讓我知道任何人都可以想到任何事情。一如以往，對社區的熱愛和欣賞。

Answer 1

考慮每個部分解決方案一個節點。只需將您使用的任何內容添加到每個節點中，並且最終將成爲答案的任何節點都將包含您使用的一組項目。

因此，每次您找到新的解決方案時，只需將項目列表設置爲新的最佳解決方案的項目列表，然後爲每個項目重複一次。

Answer 2

基本的數組實現可以幫助您跟蹤哪些項目啓用了新的DP狀態以獲取其值。例如，如果您的DP陣列是w[]，那麼您可以有另一個陣列p[]。每次爲w[i]生成狀態時，都會將p[i]設置爲您用來訪問'w [i]'的項目。然後輸出用於w[n]的項目列表，輸出p[n]，然後移至索引n-weightOf(p[n])，直到您達到0以輸出所有項目。