动态规划问题..数组分区..

问题说，

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

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

我在url动态编程3中看到了类似的问题/解释

我在pdf中有以下疑问： –

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

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

提前致谢..

您可以尝试递归处理：

给定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个比较

希望能帮助到你

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

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

  • 子集必须是连续的吗？
  • 你能忽略超过K值的子集吗？
  • arrays值是否保证为正值？
  • 数组值是否保证不同？ 那些至少与某些常数因素不同的其他值呢？
  • 最小值和最大值之间的差异是否存在约束？

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

Interesting Posts