隨機數組發生器

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也許有用。 爲了得到更好的指導，請解釋一下，它是什麼意思，它們之間的數組儘可能地不同。