设X,Y的{1,...,100n}子集，其中|X|=3n和|Y|=7n。找到A的X子集和B的Y子集，以便：它们都不是空的，|A|=|B|和sum a_i = sum b_i。
我们可以对集合进行O(n^2)求和（最大的一个是\{1,...,100n\}，尽管这个不可能，因为1+... +100n和X不包括所有数字）
每个和都有Y基数（集合大小）（来自上一个项目符号）
我们可以有一个大小为O(n)的\{0,1\}（布尔值）表，其中行表示基数，列表示数字。所以O(n) X O(n^2)意味着我们可以创建一个基数1的子集，集合的和是i
当然，第一行/第一列很容易计算
现在基本上我需要迭代所有单元格并在每个单元格中更新它们。因此，我们将得到一个总体的时间复杂度j。
我该怎么做？
我想我可以逐行迭代它；这意味着，如果我想更新单元格O(n)（也就是说，一个大小O(n^4)和T[i,j]的集合），那么我可以寻找一个大小i的集合加上一些等于j的项。
但是可能是我们已经在上一组中使用了这个术语（大小i-1）-问题！
最佳答案
你就快到了。动态编程应包含另一个参数：
让我们将DP[K,J,I]定义为第一个K元素的大小为I的子集的数目，这些元素的总和为J。这种动态编程的思想是，对于集合中的每个元素i，我们检查这两种情况-将其添加到我们的子集，而不添加它。
DP[0,0,i] = 1
DP[k,j,0] = 0
DP[k,j,i] = DP[k-1,j-S[i],i-1] or DP[k,j,i-1]
关于algorithm - 动态编程查找两个子集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39550145/