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

发布于 2024-11-17 11:43:39 字数 544 浏览 4 评论 0 原文

问题是,

给定一个大小为 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. 另外,如果我们稍微改变一下问题,我们能否使用相同的意识形态找到两个具有相同平均值的子集?

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

提前致谢..

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..

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

み零 2024-11-24 11:43:39

您可以尝试递归处理:

给定一个已排序数组 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
等等...

示例:

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

希望它有帮助

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:

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

This diminishes the total number of comparaison (that would be 2^n = 2^6=64) you only did : 12 comparaisons

hope it helps

软糖 2024-11-24 11:43:39

不幸的是,这是一个非常困难的问题。即使确定是否存在与目标值求和的单个子集也是NP 完全

如果问题更受限制,您也许能够找到一个好的算法。例如:

  • 子集必须是连续的吗?
  • 你能忽略超过K个值的子集吗?
  • 数组值是否保证为正数?
  • 数组值是否保证不同?与其他值至少相差某个常数因子怎么样?
  • 最小值和最大值之间的差异是否有一定的界限?

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?
傲鸠 2024-11-24 11:43:39

所提出的算法仅在临时数组 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 values C[i] used to get there. (It's a variation of the "Dealing with Unlimited Copies" chapter in the PDF)

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文