以動態編程算法將集合「映射」到狀態的數據結構

我正在編寫有趣的算法編碼，以確定構建N個建築物對象的最佳順序。當然，每座建築都有自己的特點（如成本，生產，施工時間......）。基於這些特徵，還存在對Building對象的全部排序。以動態編程算法將集合「映射」到狀態的數據結構

在我的動態規劃中的某個時刻，我需要一個適應的數據結構來檢索到目前爲止構建k（k < = N）Building所達到的最佳結果。我需要這個數據結構以某種方式「映射」k建築物的集合（可能排序，因爲構建建築物b1，然後是b2或b2，然後b1使我具有相同的Nk建築物，但最有可能導致不同的狀態）到「最佳狀態」到目前爲止。

我大概可以使用簡單的HashMap，但它意味着重複包含相同元素的大量集合，而不考慮[b1，b2]是[b1，b2，b3，b4]的子集合，例如。

我希望我自己做的，一個足夠清楚的，我感謝你的幫助:)

來源

2011-05-28 Jean Logeart

不是100％明確的問題，但可能有一個類BuildingSet可能有用，它可以包含Building和BuildingSet的對象？然後你可以讓BuildingSet x = [b1，b2]和BuildingSet y = [x，b3，b4]。 – Cephron 2011-05-28 15:18:57

這是不可能不知道您的解決方案的結構來回答。

但是，如果可以通過將建築物b插入位置j從（k-1）的解中獲得k的解，那麼可以簡單地將整數i映射到解決方案之間的「delta」我和i-1的解決方案，由一對夫婦表達。

但是必須明確處理deltas可能會很糟糕，因爲您需要遍歷才能獲得解決方案。你可以通過讓增量知道引用的增量（即，在k的增量的構造函數中傳遞（k-1）的增量），然後暴露執行實際遍歷的方法getSolution()來解決這個問題。

您可以將此想法擴展到類似的解決方案結構。

來源

2011-05-28 15:20:33 akappa

您可以使用LinkedHashSet作爲鍵值，該值是以迭代順序構建集合中包含的Buildings的成本。這有點破解，但根據hashCode和等於它應該工作。你更喜歡更明確地使用設置成對的成本和構建順序的hashmap。

來源

2011-05-28 15:49:15 karmakaze

如果您的解決方案看起來像ABC，cost1，ABCD，cost2，則創建鏈接列表d-> c-> b-> a。將解決方案存儲爲成本元組以及對解決方案中包含的最後一個元素（列表中最早的元素）的引用

來源

2011-05-29 06:27:43 Nicolas78

以動態編程算法將集合「映射」到狀態的數據結構

回答

相關問題