平衡值集

所以我正在研究一個有趣的小程序，並跑過這個相當有趣的問題：我有幾套預定義集合的值。這些都是更大價值池的獨特子集。每個數字子集的平均值應該儘可能接近。這並不需要是完美的，但應該足夠接近以至於所有的套都相互「平衡」。平衡值集

例如：{1,2,3,6,9,10,15,23,27}全球平均：10.66 需要被分類成2臺2和一組5

可接受的結果： {1,27} {2,23} {3,6,9,10}

在實踐中，這些值將介於60和200之間，而套將範圍從大小爲6〜20。

我已經嘗試了幾種不同的算法，並獲得了不同程度的成功，但是我很想看看StackOverflow中的優秀人物在想什麼。

我最好的，扎克

來源

2010-06-25 Zach H

我認爲，爲了測試（或品嚐）所提議的算法的好處，可能需要更詳細地指定「每個數字子集的平均值應儘可能接近於彼此」的條件。 – 2010-06-25 21:14:57

這聽起來很有趣。很想知道這是什麼實際應用。

只是可以肯定，你猜你的意思是不相交的子集和子集的總和大致相等（不是平均值）

此外，在例子中，我不明白你怎麼決定（肯定的），以使2組2和5之一。

我可以想到一個貪婪的子優化解決方案。

排序數字遞減順序順序。（較小的數字意外減去所以後來處理它們）
決定你將有的套數。不太清楚這個
通過一個經過一組元素之一，並把它們放到它有最低金額（圓羅賓在同等資金的情況下）的子集

這將永遠別放棄儘管你是最佳解決方案。

對於 1,2,3,6,9,10,15,23,27 顛倒：27，23，15，10，09，06，03，02，01

27 3 2 1 = 33

23 09 = 30

15 10 06 = 31

來源

2010-06-27 21:58:40

我正在編寫一個基於回合的策略空間遊戲，我和我的朋友都在我們的業餘時間編碼。每個玩家開始於一個由6顆行星組成的星系，中央星系由（numPlayers）* 4顆行星組成。每個行星都有幾個不同的隨機生成的屬性，但也有一個「價值」屬性，用來衡量行星對玩家的近似值。當我產生各種星系時，我想要平衡遊戲，以便沒有玩家從優秀的星系開始。因此，試圖使每個星系行星的平均值接近所有其他起始星系是至關重要的。 – 2010-06-28 13:25:26

沒問題，所以決定子集的數量。這是因爲每個星系都有一個星系。看起來像這個阿爾戈應該爲你工作。但我會建議，而不是決定給予每個玩家的價值的淨值（您可以使這個值本身隨機生成）一旦完成每個屬性生成一個隨機配額從剩餘的有價值的網絡被分配。所以你得到隨機屬性，隨機總值的星系給每個玩家。當然它對每個玩家都是同等價值的。 – 2010-06-28 14:33:52

是。您的評論指出了一個更好的策略。我同意。 – 2010-06-28 17:44:06

這使我想起RubyQuiz＃65，"Splitting the Loot"。主要的區別是，這個問題是尋找完全相等的分裂，而不是幾乎相等。也許有些解決方案可以幫助你。

來源

2010-06-28 17:52:52 AShelly

「分裂Loot」是我正在嘗試做的一個很好的例子。這與當前問題的另一個很大的區別是，一些寶石沒有分配給海盜，例如，4個海盜，每個寶石將獲得40個寶石中的6個，剩下16個寶石無人認領。 – 2010-06-28 19:09:24

回答

相關問題