找到一組數字等於數

Question

我想寫一個C＃程序，不如下：

1. 有兩個參數：對象的列表和一些
2. 遍歷列表，找到第一組對象等於數字。
3. 如果一組被發現停止迭代和回報集。

所以，我有用戶自定義對象的名單，說人是一個例子。說，Person對象有兩個字段，Name和Age。例如，

MyList 
- Person1: John, 10 
- Person2: Mary, 25 
- Person3: Mike, 35 
- Person4: Ann, 20 
- Person5: Joe, 5 

我想找到這等於給我傳遞的數量列表中的集。如果我通過在上述名單和50，我想回到PERSON2，Person4，Person5作爲一個列表。

Answer 1

這是subset sum problem。

不幸的是，它是一個NP完全，所以它沒有已知的多項式的解決方案。

然而，它確實有一個pseudo-polynomial solution, using Dyanamic Programming，即使用下一個遞歸函數：

f(i,0) = true 
f(0,k) = false (k != 0) 
f(i,k) = f(i-1,k) or f(i-1,k-weight[i]) 

如果這樣的解決方案存在與f(n,W)運行產生true，否則爲假。

動態編程解決方案填滿了一個表格，在表格滿了之後，您需要從table[n][W]中「回溯」您的步驟，以便找到哪些項目應該包含在該集合中。
有關從表格中獲取實際元素的更多信息，請參見this thread