2

问题说，

给定一个大小为 n 的数组，我们必须将数组输出/划分为总和为 N 的子集。

For E,g, 
    I/p  arr{2,4,5,7}, n=4, N(sum) = 7(given)
    O/p = {2,5}, {7}

我在 url Dynamic Programming3中看到了类似的问题/解释

我在pdf中有以下查询：-

  1. 我们如何找到总和为 N 的子集，因为逻辑只告诉子集是否存在？
  2. 另外，如果我们稍微改变一下问题，我们是否可以使用相同的意识形态找到两个具有相同平均值的子集？

任何人都可以对这个动态编程问题有所了解.. :)

提前致谢..

4

3 回答 3

1

您可以尝试递归处理：

给定一个 SORTED 数组 X={x1 ... xn} xi !=0 和一个整数 N。

首先找到仅用一个元素“制造”的所有可能性：

这里如果 N=xp，消除所有 xi st i>=p

其次找到由 2 个元素构成的所有可能性：

{ (x1,x2) .... (xp-2,xp-1)}

按总和排序并消除所有总和 >=N 并且您有规则：当 xi+xj >= N 时，xi 不能与 xj 一起使用

第三个有 3 个元素：您创建了所有尊重上述规则的部分。和同上的第 2 步等...

例子：

X={1,2,4,7,9,10} N=9

step one:
{9}
X'={1,2,4,7,9}

step 2: cannot chose 9 and 10
X={(1,2) (1,4) (2,4) (1,7) (2,7) (4,7)}
{2,7}
X'={(1,2) (1,4) (2,4) (1,7)}

step 3: 4 and 2 cannot go with 7:
X={(1,2,4)}
no sol

{9} {2,7} are the only solutions

这减少了您只做的比较总数（即 2^n = 2^6=64）：12 次比较

希望能帮助到你

于 2011-06-27T13:50:31.563 回答
1

不幸的是，这是一个非常困难的问题。即使确定是否存在与您的目标值相加的单个子集也是NP-Complete。

如果问题受到更多限制，您也许可以找到一个好的算法。例如：

  • 子集必须是连续的吗？
  • 你能忽略超过 K 个值的子集吗？
  • 数组值是否保证为正？
  • 数组值是否保证是不同的？与其他值的差异至少有一些常数因素呢？
  • 最小值和最大值之间的差异是否有界限？
于 2011-06-27T16:57:44.290 回答
0

所提出的算法在临时数组中仅存储一位信息T[N]，即它是否完全可达。显然，您可以在每个索引处存储更多信息[N]，例如C[i]用于到达那里的值。（这是 PDF 中“处理无限副本”一章的变体）

于 2011-06-27T13:59:05.007 回答