子集問題 - 任何材料？

Question

是的，這是一項家庭作業/實驗作業。 我很感興趣提出/發現一個算法（我可以理解：P）使用「回溯」來解決子集求和問題。

任何人都有一些有用的資源？我花了最後一個小時左右的時間用Google搜索，並不像找到我認爲可以實際使用的東西。 xD

謝謝！

Answer 1

將數據放入向量中。

然後編寫一個包含3個參數的例程：矢量，索引和和。 調用這個例程使用以下參數：向量，0，0。

的例程應執行以下任務：

• 檢查，如果我們達到了向量（指數==大小）結束。如果是這樣，我們可以立即返回。
• 呼叫本身與參數：矢量，索引+ 1，總和+矢量[指數] （在這種情況下，我們的索引處添加的元素的總和，並繼續用該載體）
• 呼叫本身與參數：矢量，

我特意在這種算法忽略了2份指數+ 1，總和 （在這種情況下，我們沒有索引的總和，在添加的元素，但仍然繼續）：

• 首先，您應該在某個時候檢查總和。如果它是零，那麼你發現了一個正確的子集秒，你應該也傳遞關於你使用哪些元素的知識，所以如果和爲零，你可以打印出子集。考慮爲此使用STL :: set。

或者，您可以使用該函數的返回值來確定是否已找到正確的子集。

該算法的複雜性是O（2^N），所以對於大集合它會很慢。

玩得開心。