遞歸揹包（分而治之）

-1

我一直在想這個問題已經超過3天了。這是我的雙胞胎任務的一部分。不過，我碰到了一個路障。任何幫助將不勝感激。分配的遞歸揹包（分而治之）

細節，我至今想通了：

我必須使用一個項目類，它定義（get和set）的重量和的東西值
表ArrayList中持有
項目陣列的價值和重量stuffList
檢查最大值東西（貪婪）適合袋的容量內，從
表ArrayList中添加這玩意指數在包裏arrayList
返回包arrayList。

到目前爲止，我已經寫的方法（似乎沒有奏效）：

Public static ArrayList <Integer> greedySelection (Item[] stuffList, int Capacity) 
 
{ 
 
\t \t ArrayList<Integer> bag = new ArrayList<Integer>(); 
 
\t \t ArrayList<Integer> Table = new ArrayList<Integer>(); 
 

 
\t \t for(int i = 0; i < Table.size(); i++){ 
 
\t \t \t if(Table.get(i) < Capacity){ 
 
\t \t \t \t bag.add(i); 
 
\t \t \t \t Table.remove(i); 
 
\t \t \t } 
 
\t \t } 
 
\t \t return bag; 
 
}

來源

2015-11-03 OJNaire

提示：你創建一個空列表，爲每個元素做一些事情（沒有任何東西，它仍然是空的），然後返回。 –

另外，你是否知道你現在擁有的既不是遞歸也不是貪婪？ –

歡迎來到StackOverflow。請閱讀並遵守幫助文檔中的發佈準則。 [MCVE]（http://stackoverflow.com/help/mcve）適用於此處。在您發佈代碼並準確描述問題之前，我們無法有效幫助您。具體而言，您沒有追蹤執行併發布輸出。如果你有，你會看到基本的問題。最重要的是，這個例程不是遞歸的：它不會調用它自己。 – Prune

你的代碼中有幾個問題。您沒有專注於遞歸算法的基本原則：

檢查是否「觸底」。
如果是這樣，返回簡單的結果。
如果沒有，那麼做一個瑣碎的操作和重複的剩餘任務。

對於這個套路，你需要弄清楚

當你已經「觸底」：當你不能添加任何其他內容。
此時的簡單結果是什麼？只需返回現有的包包？
重複發生時，您可以添加您可以放入包中的最有價值的物品（貪婪），並以新的事態稱呼自己。這是什麼情況？至少需要調整項目列表，包內容和剩餘容量。

請注意，您的初始狀態必須在調用程序中設置並傳入例程。

這會讓你感動嗎？

來源

2015-11-04 22:09:39 Prune

遞歸揹包（分而治之）

回答

相關問題