动态规划问题..阵列分区.. [英] Dynamic Programming Problem.. Array Partitioning..

问题描述

现在的问题说，

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

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

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

和我在的PDF以下查询： -

  

    

    
1. 我们如何能找到这一笔N，作为逻辑只是告诉子集是否存在子集不？
    
2. 此外，如果我们改变的问题了一下，可以发现两个子集具有使用相同的意识形态？
等平均     

  

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

在此先感谢。

解决方案

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

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

• 请的子集必须是连续的？
• 您可忽略的子集超过的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:-

1. How could we find the subsets which sum to N, as the logic only tells whether the subset exist or not?
2. Also, if we change the question a bit, can we find two subsets which has equal average using the same ideology?

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?

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