问题是,
给定一个大小为 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中有以下疑问:-
<块引用>
- 我们怎样才能找到总和为 N 的子集,因为逻辑只告诉子集是否存在?
- 另外,如果我们稍微改变一下问题,我们能否使用相同的意识形态找到两个具有相同平均值的子集?
任何人都可以对这个动态编程问题有所了解吗..:)
提前致谢..
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:-
- How could we find the subsets which sum to N, as the logic only tells whether the subset exist or not?
- 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..
发布评论
评论(3)
您可以尝试递归处理:
给定一个已排序数组 X={x1 ... xn} xi !=0 和一个整数 N。
首先找到所有“制造”的可能性“只有一个元素:
这里如果 N=xp,消除所有 xi st i>=p
第二 找到由 2 个元素构成的所有可能性:
{ (x1,x2) .... (xp-2,xp-1)}
按总和排序并消除所有总和 >=N
并且您有规则:当 xi+xj >= N
Third 具有 3 个元素时,xi 不能与 xj 一起使用:
您创建的所有部分都遵守上述规则。
同上步骤2
等等...
示例:
这会减少比较的总数(即 2^n = 2^6=64),您只做了:12 次比较
希望它有帮助
You can try to process recursively:
Given a SORTED array X={x1 ... xn} xi !=0 and an intger N.
First find all the possibilities "made" with just one element:
here if N=xp, eliminate all xi s.t i>=p
second find all the possibilities made with 2 elements:
{ (x1,x2) .... (xp-2,xp-1)}
Sort by sum and elminate all the sums >=N
and you had the rules: xi cannot go with xj when xi+xj >= N
Third with 3 elments:
You create all the part that respect the above rule.
And idem step 2
etc...
Example:
This diminishes the total number of comparaison (that would be 2^n = 2^6=64) you only did : 12 comparaisons
hope it helps
不幸的是,这是一个非常困难的问题。即使确定是否存在与目标值求和的单个子集也是NP 完全。
如果问题更受限制,您也许能够找到一个好的算法。例如:
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:
所提出的算法仅在临时数组
T[N]
中存储一位信息,即它是否可达。显然,您可以在每个索引[N]
处存储更多信息,例如用于到达那里的值C[i]
。 (这是 PDF 中“处理无限副本”一章的变体)The proposed algorithm stores only a single bit of information in the temporary array
T[N]
, namely whether it's reachable at all. Obviously, you can store more information at each index[N]
, such as the valuesC[i]
used to get there. (It's a variation of the "Dealing with Unlimited Copies" chapter in the PDF)