所以我有n个正整数(c_1，...，c_n)的给定集合C。任务是找到C的两个子集A和B，其中A仅包含正数，而B仅包含C中数字的负数。然后，两个子集A和B的总和应为数字d(d总是积极的)。我需要找出是否有两个这样的子集，如果有，它们包含哪些数字。For example: {3, 5, 6, 13, 24} // d = 12 => solution: true: {5, 13} {-6}
我知道这是子集总和问题的一种变体，我已经看到了类似问题(带有负数的子集总和)的一些解决方案，但是我需要使用动态编程来解决该问题。我见过的大多数解决方案都适用于递归，而不适用于DP。
我想我需要一个大小为(n * n * d)的3D布尔表S(i，j，k)。但是S(i，j，k)何时为真，何时为假？因为我总是需要检查所有可能的方法来使用k数来计算总和，所以它们可以是正数也可以是负数(例如:对于4个数字{1,2,3,4}，有2 ^ 4种排列方式他们:1 + 2 + 3 + 4，1-2 + 3 + 4，1-2-3 + 4，...，-1 + 2-3-4，1-23-4)
我的想法是否正确，或者我已经做错了事？
最佳答案
一种方法是在由(c_1，c_2，...，c_n，-c_1，-c_2，...，-c_n)组成的集合上使用标准动态规划子集和算法。
这将找到一个总和为d的子集(或证明不存在)。
将A设置为子集中的所有正数，将B设置为所有负数。
您可能还希望删除A和B中都出现的任何数字(例如，如果A中有3，B中有-3，则可以在不更改总和的情况下删除两者)。