創建多個總計爲100的組合

我希望能夠創建多個總和爲100％的組合，只要給定了具有定義的「差異因子」的「桶」數量。在下面的例子中，差異是20的一個因素，使得它很簡單，但我可能會在最終解決方案中將其降低到1。創建多個總計爲100的組合

例如，對於3「桶」 A，B，C，你可以有：

A  100  80  80  60  60 ... 0 
B  0  20  0  20  40 ... 0 
C  0  0  20  20  0 ... 100

每一列是一個組合（求和到100），我想存儲和做進一步的計算。

這是一個業務問題，而不是作業。

請幫我想出一個解決方案。蠻力的方式是爲每個可能的組合創建一個多維數組，例如100x100x100，然後再通過每一百萬個組合，看看哪一個總和爲100.但是，這看起來效率太低了。

非常感謝。我希望我已經解釋清楚了。

來源

2011-03-09 RyanH

考慮到你的第一個超過了100，yo的意思是總和爲100％。由於它不是一個因素，你也不清楚你的mea是什麼因素 - 你的意思是相鄰桶之間的差異需要是+還是 - 差異「因素」？ – 2011-03-09 12:00:08

@Paul列加起來最多爲100 – Harold 2011-03-09 12:01:53

http://stackoverflow.com/questions/3510586/algorithm-to-calculate-the-number-of-combinations-to-form-100的副本。即使這些數字完全相同（100,20）。你確定這不是作業嗎？還是你是另一個問題海報的同事？ – Patrick 2011-03-09 12:28:36

這個問題被稱爲partitions而不是組合，這是不同的。

首先：「差異因素」只是將問題從找到100分區（在您的示例中）找到5分區（然後乘以20）。

下一步：如果桶的數量是恆定的，你可以這樣做（僞代碼）：

for i = 0 to n 
    for j = 0 to n-i 
    output (i, j, n-(i+j))

如果桶的數量將是動態的，你必須要有點更聰明，但這種方法基本上可行。

來源

2011-03-09 12:08:16 AakashM

非常感謝。這比我想象的有用並且不那麼複雜。 – RyanH 2011-03-09 14:05:47

然而，看着它，桶的數量並不是恆定的。如果我們考慮5個桶，計算時間太長。回到我的繪圖板... – RyanH 2011-03-09 14:06:47

如果我們考慮五桶，答案的數量也高得多！實際上，它應該以桶的數量呈指數級增長（按大O計算）...... – sclv 2011-03-09 17:19:31

算法明智的，你可以讓所有0和100之間的數字在列表中有20列出的步驟，然後使列表A的副本是列表B.

接下來，比較每個列表的的列表B查看哪些值合計爲100或更少，並將這些記錄存儲在列表C中。接下來，執行相同的操作以再次列出C（檢查0和100之間的所有值，步驟爲20），以查看哪些值加起來爲100.

來源

2011-03-09 12:01:34 Harold

這看起來很適合緩存和動態編程。

fun partition (partitions_left, value): 
    if partitions_left == 0 
    return empty_list 

    if value == 0: 
    return list of list of partitions_left 0 elements 

    return_value = empty_list 
    for possible_value from value downto 1: 
    remainder = value-possible_value 
    children = partition(partitions_left-1, remainder) 
    for child in children: 
    append (cons of possible_value and child) to return_value 

    return return_value

如果你還要確保你從緩存投放已計算出的值，「所有」，你需要做的則是生成所有生成的分區的所有可能的排列。

來源

2011-03-09 13:22:57 Vatine

創建多個總計爲100的組合

回答

相關問題