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

Question

问题是，

给定一个大小为 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. 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?

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

提前致谢..

Answer 1

可以尝试递归处理:

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

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

这里如果N=xp，则消除所有xi s.t i>=p

second 找出由 2 个元素构成的所有可能性:

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

按总和排序并消除所有总和 >=N你有规则:当 xi+xj >= N

时，xi 不能和 xj 一起去

Third 有 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 次比较

希望对你有帮助