动态规划问题..阵列分区..

问题描述

现在的问题说，

这给定大小为n的数组，我们要输出/分区排列为子集其总和为n。

 对于E，G，
    I / P改编{2,4,5,7}中，n = 4，N（总和）= 7（给出）
    O / P = {2,5}，{7}
 

我看到了类似的问题/解释在URL 动态Programming3

和我在的PDF以下查询： -

任何人都可以扔一些光对这个动态规划问题..：）

在此先感谢。

解决方案

不幸的是，这是一个非常棘手的问题。即使确定如果存在一个子集，总结你的目标值是的。

如果问题更受限制，你也许能找到一个好的算法。例如：

• 请的子集必须是连续的？
• 您可忽略的子集超过的K值？
• 是数组值保证是正的？
• 是数组值保证是不同的？怎么样，至少一些常数因子从其他值不同？
• 是否有某种必然的最小和最大的价值之间的差额？

The question says,

That given an array of size n, we have to output/partition the array into subsets which sum to N.

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

I saw similar kind of problem/explanation in the url Dynamic Programming3

And I have the following queries in the pdf:-

Can anybody thrown some light on this Dynamic Programming problem.. :)

Thanks in Advance..

解决方案

Unfortunately, this is a very difficult problem. Even determining if there exists a single subset summing to your target value is NP-Complete.

If the problem is more restricted, you might be able to find a good algorithm. For example:

• Do the subsets have to be contiguous?
• Can you ignore subsets with more than K values?
• Are the array values guaranteed to be positive?
• Are the array values guaranteed to be distinct? What about differing from the other values by at least some constant factor?
• Is there some bound on the difference between the smallest and largest value?

这篇关于动态规划问题..阵列分区..的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！