給定數字和間隔集合的分配算法

我在尋找一種算法，它可以處理下面描述的問題。我已經寫了一個算法（這個算法過於專業化，不能發佈，我想），儘可能優化我的想法，但是對於更大的數字集合，它仍然太慢（因爲成本會成倍增長）。解決方案應該在一臺體面的計算機上不超過5秒。給定數字和間隔集合的分配算法

你給定的一組數字，例如：

M = {1，1，1，2，2，2，5,5，5，10，10，10，10，20， 50，50，...,1000000,10000,20000,20000}

不必具有特殊的結構（儘管它們在這裏）。

你給定一組的「目標點」，也是數字，如：

P = {670，2010，5600，10510，15000}

的目標是，採取至少 M中的數字數量，其中，當您按決定的順序添加它們時，您會得到中間結果儘可能接近，以便P中的所有點。您只能使用M中的每個數字一次。

在我們的例子中，一個可能的解決方案（雖然我不知道如果這是最好的）：

Y =（500，100，; 1000，200，200，2000，1000 ，500; 5000; 2000，2000年）

正如你所看到的，兩個標準至少和密切爲某種權衡。這就是爲什麼我現在的算法使用評分來找到「最好」的解決方案。

下面是它目前是如何工作的：

排序男，排序P，上升
刪除號碼太小，貼切變化得分或者是太大了
遞歸數：
起飛P中的下一個點作爲當前的「目標」，加上減去例如10％
添加下一個號碼出去M的，去掉它如果M
當目標點附近，轉到4.如果在終點，計算電流分佈的得分，並可能記住它
，否則，轉至5
試圖從數量回來的時候，需要一個較大編號

它從不試圖兩個相同的號碼，只嘗試了升序排列，如：

100，100，100，50，50，20，10
100，100，100，50，50，20，20
100，100，100，50，50，50 ，10
100，100，100，50，50，50，20
100，100，100，50，50，50，50
100，100，100，100
100,100 ，100,100,10
100,100,100,100,20
...

，每個編號約5，和刪除許多小的數字，該算法實在是快，找到一個很好的解決方案。但是當我添加更多數字或者特別包含更小的數字時，運行時間從100ms增加到無窮大。

你能給我一個提示，該如何處理這個問題？文獻中是否有類似的算法可以處理這個問題或其中的一部分？

來源

2009-08-15 Wikser

我應該補充說，得分是近似值，而不是真正找到最高分的解決方案的目標。但是，由於得分現在不計算數字，這些數字本身是有意義的（與其他分數相比），最高是我能想到的唯一方法。也許可以停止評估當前路徑，如果評分不會改變*太多*。 – Wikser 2009-08-15 06:14:01

到硬幣找零問題類似：http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro.htm

唯一的區別是，你必須的「硬幣」（可通過標記的物品陣列爲「已使用」中很容易地解決），並且您有限的供應不需要達到確切的數字 - 加/減10％對你有好處（這樣你就可以丟掉M中小於目標值10％的元素）

來源

2009-08-15 13:13:35 DmitryK

感謝您的提示。「有限」數量的硬幣是問題的一個主要部分，因爲我不能想出一種方法來對可能的「變化」使用動態編程（記憶），因爲它們取決於剩下的硬幣（這非常有用許多組合要記住和比較）。：/ – Wikser 2009-08-16 05:51:33

這有點類似於Knapsack Problem。

來源

2009-08-15 06:35:38 caf

它由多個揹包問題組成，它們相互作用：「從間隔A取一個數字並將其置於間隔B是否更好？」我希望有一些額外的約束可以降低複雜性。 – Wikser 2009-08-15 08:23:42

讓我試試，它可能不是最好的，但應該很好地工作。我使用PHP在這裏 -

1）進行分類M中的價值和他們的計數：讓它命名爲c

$C = array_count_values($M); 

This gives us: 
Array 
(
    [1] => 3 
    [2] => 3 
    ... 
    [20] => 1 
    ... 
)

2）與P拿起第一個數字和M上應用binary search並獲得最接近P1的編號N1（N1 < P1）。由C

So say you get 500 which is nearest to 670. Now subtract $C[500] - 1. 
You can validate if count is not 0 and if zero get the next lower number from M.

3）獲取P1-N1，並再次二進制搜索減去相應的計數此號碼，並返回最近的值。將此添加到N1並保持循環，直到您獲得最接近的總和。

4）重複第2點和P的所有成員3點

二進制搜索的關鍵部分在這裏，應該是足夠的效率。

來源

2009-08-15 08:04:47

給定數字和間隔集合的分配算法

回答

相關問題