随机数组发生器

Question

给定'n'，'m'，'k'，'x'和'y'整数值...
我有一个数值ArrayList'n'的位置，我需要创建'k '使用第一个数组中的值和'm'个位置的其他数组。我该怎么做才能确保数字的总和为'x'，最大误差为'y'，并且数组之间尽可能不同？

我将在测试生成器中使用它来随机化问题。这些数字代表了难题。当我试图做到这一点时，我随机化了情况并检查它们是否正确，但这非常缓慢。有人知道更好的方法来做到这一点？

Answer 1

你有一些不到n!/(m! . (n-m)!)可接受的解决方案，其中挑选最不同的解决方案。

1. 的可能候选方案坚持偏差的平方和y的最佳成本。

2. 对于固定数量的可能解决方案，选择最终解决方案，其中 与以前接受的最终解决方案的差异最小：相同条目的难度总和。 （这只是局部最优，但应该做的。）

排序上降低难度N＃列表。 原则上针对m＃子列表迭代n!/(m! . (n-m)!)。

根据允许的范围更改考生：跳过/失败超出范围。

Answer 2

从您的描述中，它听起来像是离散背包问题的变体。基本上你可以搜索一个修改DKP的几个解决方案 - 如果有更多K的解决方案你可以删除更多的解决方案，如果更少的话 - 你可以对那些你获得的产品进行排序。

天真的实现将搜索从n = x-y到x + y的DKP解决方案，然后按照上面所述处理它们，但它可能确实很慢。您可能会在数学堆栈交换中获得一些更好的解决方案。

Answer 3

首先对你的数组进行排序，然后找到离我最近的X/m最近的元素的值。

查找米最接近编号以mid.or使用这种想法

所以设置源点等于中间：

对（INT I = 0;我< N;我++）

{ A [1] = A [1] -mid}

现在需要m个该数字的总和是零，见link1 & link2 & link3也许有用。 为了得到更好的指导，请解释一下，它是什么意思，它们之间的数组尽可能地不同。