解決此問題的最佳算法是什麼？我在這個問題上花了幾個小時。但無法解決。對數值進行分類的算法
一個男人購買了一條項鍊，並計劃將它分成兩部分，每部分的平均亮度應該大於或等於原始部分。
用於將項鍊的標準是在珍珠的數目
1.差兩個珍珠之間套不應珍珠在原項鍊的數量或3取高者的大於10％。
2.兩個項鍊中珍珠數量的差異應該是最小的。
3.如果任何一條項鍊的平均亮度小於原始設置的平均亮度，則返回0作爲輸出。
4.兩個項鍊的平均亮度應該大於原來的兩個，兩塊的平均亮度之差最小。
5.每件的平均亮度應大於或等於原件。
這個問題很難有效地做到（在NP某處）。
假設你有一組平均值爲X。那就是，X = (x1 + x2 + ... + xn)/n。
假設您將它分成平均分別爲S和T的集合，其中s和t項目分別在每個集合中。
您可以用數學證明，如果平均的一個，S或T，比X越大，其他兩個必須小於X。
因此，兩組必須具有完全相同的亮度，因爲這是您的條件可滿足的唯一方法。
知道了這一點，你最後的sumset sum問題 - 你想找到一個子集，其總和恰好是整個集合的一半。這是一個衆所周知的難題。 （它已被歸類爲NP，好吧，它與子集和問題並不完全相同，但是如果從每個亮度值中減去全集的平均值，則解決子集和問題會給出答案。相反，看你如何解決你的問題的子集總和問題。）
因此，沒有快速的方法做到這一點 - 只有近似值或指數運行時間...但是，也許this將幫助。它提到更好運行時間如果你的權重（在你的情況下，亮度水平）是有界的
告訴我們你是如何測量「亮度」，因爲規範的計算平均值的方式將使分區的平均值的平均值無法大於平均值本身藝術比原來的平均水平高，另一部分必須低一些 - 也就是說，你必須把項鍊分成兩半，以達到你想要的結果。 – Kaganar 2012-03-30 20:15:44
@Kaganar - 輸入值將是一組數字，例如 - {10,6,3,9,7,2,5,8,4,1}，其中0≤亮度≤10。 – eler 2012-03-30 20:19:09
你打算把這個分成兩部分，每部分的平均值等於或大於原始平均值？ – Kaganar 2012-03-30 20:20:06