java - 随机数组生成器

Question

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

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

Answer 1

根据您的描述，这听起来像是离散背包问题的一种变体。基本上，您搜索修改 DKP 的几种解决方案 - 如果它们中的 k 个更多您可以删除其他的，如果更少 - 您可以置换您获得的那些以生成更多。

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

Answer 2

首先对你的数组进行排序。然后找到最接近我称之为中间的 X/m 的元素的值。

找到最接近 mid.or 的 m 数。或者使用这个想法

所以设置源点等于中间：

对于 (int i=0; i < n ; i++)

{ a[i]=a[i]-mid }

现在您需要 m 个数字之和为零的数字，请参阅链接1和链接2和链接 3可能有用。为了获得更好的指导，请解释您的意思是阵列之间尽可能不同。

Answer 3

您有一些不太n! / (m! . (n-m)!)可接受的解决方案，从中挑选出最不同的解决方案。

1. 可能的候选解决方案遵循与 y 的偏差平方的最优成本。

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

按难度递减对 n# 列表进行排序。原则上迭代 m# 个子列表n! / (m! . (n-m)!)。

更改允许范围内的候选人：跳过/失败超出范围的候选人。