問題
我正在嘗試回傳N 個最佳答案（對于我想要 250 的確切數字）。根據我對動態編程的理解，它將回傳一個最佳答案。所以我相信我必須使用回溯來生成 N 個最佳答案。
對于背包變體問題，我有一個物件組合不應通過的最大重量。我有4 組物件，并且必須從每組中選擇一個以在不超過重量限制的情況下給出最高值。集合中的每個物件都有一個值和一個權重。
這些集合有 164、201、90 和 104 個物件，這意味著有 308,543,040 種變化可供嘗試。我實作了一個蠻力演算法，但它需要很長時間。
優化嘗試
到目前為止，我的優化嘗試是通過增加權重排序來預處理輸入集。（最低優先）。在添加每個物件時，如果約束權重大于物件的組合權重，那么我可以跳過集合的其余部分，因為所有其他選項都將無效。這可以在遞回函式的任何級別運行。
我還有一個最小堆來存盤我找到的最大值。如果四個物件的組合小于堆頂，則不會添加。否則，pushpop 到堆。我不確定是否可以使用它來進一步優化回溯，因為它需要選擇所有四個物件。它更多地用作驗證，而不是提高速度。
問題
- 我可以通過回溯進行任何其他優化來加快尋找 N 個最佳答案的程序嗎？我是否已經用盡了優化并且應該只使用多個執行緒？
- 是否可以使用動態編程？如何修改動態規劃以回傳 N 個最優選擇？
- 還有其他演算法要研究嗎？
uj5u.com熱心網友回復：
由于必須從每組中選擇一個專案，您可以嘗試以下優化：
- 讓集合成為
A,B,C,D。 - 從集合中創建專案的所有組合，
A,B并一起創建集合C,D。假設串列具有 length ，這將具有O(n^2)復雜性n。讓組合串列成為X現在Y。 - 排序
X和Y基于重量。您可以使用諸如累積陣列之類的東西來跟蹤在給定權重下具有最大可能值的組合。（其他資料結構也可能用于相同的任務，這只是強調基本思想的建議）。 - 創建一個最大堆以存盤具有最大值的組合
- 對于 中的每個組合，在其權重為 的約束下選擇具有最高值
X的組合。根據此組合的值，將其插入最大堆中。Y<= target weight - X_combination_weight
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/466280.html