使用动态规划对列表进行划分
我之前在这里发过一些关于我正在尝试的项目的内容，但我一直遇到设计上的问题，得从头开始设计。所以我想问问，能不能把我想做的事情发出来，希望有人能帮我理解一下，怎么才能得到我想要的结果。
背景：
我刚开始学习编程，正在努力学习。我选择了一个我感兴趣的项目，主要是把一个列表中的每个数字拆分开，只用列表里的数字。我知道我可以用暴力破解的方法来解决这个问题（我确实这么做过），但我还想学习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]]}
这个方法的逻辑是，它不会花时间去计算列表中下一个可能的数据，所以如果我发送一个包含一百万个数字的列表，它可以快速处理，甚至可以扩展到Hadoop集群。
我创建的代码可以让这个工作正常运行，具体内容可以在这里找到，但那个问题是关于如何修正设计问题。我得到了建议说这是一个分区问题，我查了一下，发现了很多更简单的版本（activestate），但这并不是我想做的，因为它只是拆分一个数字，并没有使用特定的数据集来完成。
问题：
希望我能清楚地描述我想做的事情。我需要阅读/学习/了解什么，才能用动态规划在Python中创建一个列表的分区表，以便它可以扩展？这只是一个爱好，不是时间紧迫的事，但我觉得我已经在这个问题上花了超过三个月的时间，每次都遇到设计问题，导致我不得不从头开始。我该如何正确构建这个（想看看我错误的方法可以参考我上面的链接）？我在网上搜索过，找到了关于背包问题和分区问题的解决方案，但它们似乎更适合学校作业，而不是为了处理大数据集而设计的。
希望有人能给我一些见解，但无论如何，谢谢你阅读这些内容。
1 个回答
你需要知道，动态规划（DP）问题并不一定适合独立和分布式计算。
当你考虑经典的动态规划算法时，你会用到一个矩阵、表格或数组，然后按照一定的顺序逐步计算新的值。每次计算一个值都需要依赖之前计算好的其他值。因此，你失去了数据的独立性，最多只能同时计算一定数量的数组字段，这取决于具体的动态规划算法。例如，很多动态规划算法可以并行处理整个表格的一列，因为每个字段都依赖于前一列的字段。但这已经是极限了，因为在那一列之后，所有剩下的字段都相互依赖。
也就是说，计算你列表中各种数字的和的可能性并不是一个动态规划问题。你并没有解决任何子问题，而只是简单地收集所有可能的和（如果它们恰好与列表中的某个值匹配）。
因此，我建议你采取以下稍微不同的方法：
- 计算一个新列表，包含所有可能的和。这是数据独立的，可以并行处理，但你需要一个终止的上限。举个例子：
[1,2,4]会变成[ [1],[2],[4],[1,1],[1,2],[1,4],...]。你不需要明确构建这个列表，只需将每种组合传递到下一步。 - 评估每次计算，也就是计算和并检查它是否与原始列表中的某个值匹配。同样，你是数据独立的，可以独立进行所有这些计算。
- 将所有正结果合并到最终的数据结构中。
所以总结一下，回答你的问题：
- 重新考虑一下，你是否真的想把这个问题看作动态规划。
- 你可能想了解一下数据并行性。这在用GPU解决这类问题时特别相关，所以关于CUDA/OpenCL的相关文献也可能会对你有帮助。