保存已計算的值

基本上，我有一個項目列表，其中包含大小和值的參數，需要以最佳方式適合大量其他項目，才能達到儘可能高的值，但保持在maxSize之下。保存已計算的值

要解釋該問題，請參閱以下說明。

項目1：大小1，值1;

項目2：尺寸2，值4：

最大值：11;最好的解決方案：1xItem1，5xItem2。

但在這種情況下，限制更高，項目更多。我的問題是要找到最好的組合。到目前爲止，我已經創建了一個這樣的算法，但是由於複雜性非常糟糕，它只適用於幾個項目。

我基本上都在嘗試每種可能的組合，這會在更多數量的項目上創建大量計算。我將路徑保存爲一個字符串（Item2-> Item2-> Item1-> Item2 ...），直到總大小高於極限。如果該值高於某個其他找到的值，則將其保存爲字符串。

我想要做的是保存所有已經完成的計算，這裏是一個例子。

A - > A - > A - > A - >甲

A - >乙 - > A - > A - >甲

在最後一種情況，沒有必要重新計算A - > A - > A，我想要做的就是保存它。

這樣做的最好方法是什麼？

目前，我的遞歸看起來像這樣

recursion(Item item, int size, int value, String s){ 
    s += cust.getName() + "-"; 
if(value is bigger) 
    bestMix = s 



for(Item item : itemList){ 
     if(!(we break the limit){ 
      recursion(item, size + item.getSize(), value + item.getValue(), s); 
     } 
    } 
}

我想要做的，就是取已經計算出的值做遞歸時。

什麼是最簡單最聰明的方法來降低時間複雜度？

來源

2013-10-26 oalsing

你在找什麼叫做memoization，dynamic programming變種的常用算法技術，可以讓你通過重複使用子問題的解決方案來提高速度。這種技術的一個必要條件是解決的問題有一個optimal substructure，這是你的問題。

以下是memoization通常實現的一種方法：向遞歸例程添加一個額外參數，該例程包含解決已知子問題的映射。將每個子問題的參數編碼爲一個鍵，以在已知解決方案的地圖中查找。

memoized遞歸解決方案的第一件事是構造一個鍵並在已知解決方案的映射中運行查找。如果答案在那裏，它會馬上返回而不會再遞歸下去。如果答案不存在，則按照常規方式進行計算，然後在遞歸調用返回之前放置在解決方案的映射中。

來源

2013-10-26 14:53:15 dasblinkenlight

謝謝。我正在考慮實施備忘錄，但不知道這是否正確。我會研究記憶並嘗試讓事情繼續下去。感謝您的答覆。 – oalsing

項目1有每個規模的利潤（雙值/大小（1/1。項目2有一個更大的每個規模的利潤4/2。所以你應該排序你的itemList（與Comparator）與項目2第一然後第一個遇到的解決方案可能是最大的。

另一個改進是也對每一個項目一個int factor，開始嘗試用最高的因素。

一般遞歸已經對事情的參數完成，和待辦事項（候選人）

隨着每次調用遞歸，結果。訪問其餘部分的緩存可能是可行的，但對於已經存在的數據結構（比如某些樹結構）來說更是如此。

來源

2013-10-26 14:43:20

正如dasblinkenlight所說，memoization是要走的路，但我決定做別的事情。

我意識到，我的問題是同文以「未綁定揹包問題」點擊此處瞭解詳情： http://www.cs.rit.edu/~zjb/courses/800/lec7.pdf http://en.wikipedia.org/wiki/Knapsack_problem

我與動態規劃解決。 http://en.wikipedia.org/wiki/Dynamic_programming

這使我的時間複雜性好多了。

來源

2013-10-27 17:36:05 oalsing

保存已計算的值

回答

相關問題