使用動態編程對列表進行分區

Question

我在這裏發佈了一些與我一直在嘗試工作的項目相關的內容，並且我一直在打擊設計問題，並且必須從頭開始設計。所以我想知道我是否可以發佈我想要做的事情，並且有人可以幫助我理解我如何獲得我想要的結果。

背景：

我新的編程和努力學習。因此，我參與了一個對我感興趣的項目，其中涉及基本上使用列表並僅使用列表中的數字來分解每個數字。我知道我可以很容易地蠻力（這是我做的），但我也想學習Hbase，Hadoop和並行處理，所以我希望能夠通過各種機器打破這個過程。我認爲這樣做的方式是使用動態編程和遞歸來創建可能進一步細分的可能性表。

例子：

如果我提交名單：[1,2, 4]我應該得到{1: [[1]], 2: [[1, 1]], 4: [[2, 2]]}。它的基本意思是2 + 2 = 4，1 + 1 = 2，1 = 1 ..因此，我試圖查看所有的方法來創建4，我可以查找這個列表（它將在數據庫中）和看2 + 2 = 4，然後分解2 ..等等..我有查找工作工作，但我有問題的故障。使用蠻力不會讓我使用大數字（比如說百萬，列表中有一千個數字），這樣我就可以使用hadoop或其他工具來擴展它。以下是可能的結果更多的例子：

[1,2, 3, 4] = {1: [[1]], 2: [[1, 1]], 3: [[1, 2]], 4: [[1, 3], [2, 2]]} 
[1,2, 3, 4, 6, 10] = {1: [[1]], 2: [[1, 1]], 3: [[1, 2]], 4: [[1, 3], [2, 2]], 6: [[2, 4], [3, 3]], 10: [[4, 6], [2, 2, 2, 2, 2]]} 
[10, 30, 50] = 50: [[10, 10, 30]], 30: [[10, 10, 10]]} 

這種方法的邏輯是，它不會花時間在列表中COMPUT下一個可能的數據，所以如果我發送列表一百萬的數字它可以快速做到甚至擴展到hadoop集羣。

我創建的代碼是here，但問題在於如何糾正設計問題。我得到了這樣的建議：這是一個分區問題，並且環視四周，發現了我想要做的更簡單的版本（activestate），但它並不完全是我想要做的，因爲它分解了一個數字，並沒有使用特定的數據集來做到這一點。

問：

所以希望我清楚地描述了我想要做的事。我需要閱讀/學習/學習如何使用動態編程在python中創建列表的分區表，以便擴展？它只是一種業餘愛好，而不是時間敏感，但我覺得我已經在這方面工作了3個多月，每次遇到設計問題時都必須從頭開始。我如何正確構建這個（看我的不正確的方式看到我的鏈接上面）？我已經搜索並找到了揹包問題和分區問題的解決方案，但它們似乎更適合於學校工作，並且不是真正用大數據集來擴展。

希望有人能給我洞察力，但不管感謝您閱讀本文。

Answer 1

您必須知道，DP問題本身並不是最佳的獨立和分佈式計算。

當你考慮DP算法的經典形式時，你有一個矩陣/表/數組，並且你以一定順序連續計算新值。每個值的計算都需要先前創建的其他值。因此，您將失去數據獨立性，並且可以同時最大限度地計算一定數量的數組字段，具體取決於特定的DP算法。例如，許多DP算法可以並行處理整個表格列，因爲每個字段都依賴於前一列的字段。但這已經是由於該列之後的所有剩餘字段的數據依賴性所引起的限制。

這就是說，計算列表中可用的各種數字的總和可能性不是DP問題。您根本沒有解決任何子問題，只是簡單地收集所有可能的金額（如果它們碰巧與您的某個列表條目匹配）。

因此，我建議以下悅目不同的方法：

• 計算所有可能的總和一個新的列表。這是數據獨立的並且可以並行化，但是您需要一些上限來終止。例如：[1,2,4]變成[ [1],[2],[4],[1,1],[1,2],[1,4],...]。您不必明確地構造這個列表，而只需將每個這樣的組合傳遞給下一步。
• 評估每個計算，即創建總和並檢查它是否與原始列表中的值匹配。同樣，您獨立於數據，可以獨立執行所有這些計算。
• 將正面結果結合到最終的數據結構中。

所以總結起來，並回答您的問題：

• 反思，你是否希望把這個問題作爲DP的。
• 您可能想要了解數據並行性。這在解決GPU的這些問題時特別重要，所以關於CUDA/OpenCL的相關文獻也可能有用。