查找給定的一組整數的總和達到給定總和的所有組合

-1

我正在尋找對以下問題的答案。查找給定的一組整數的總和達到給定總和的所有組合

給定一組整數（無重複項）和一個和，找出該組元素的所有可能組合總和。解決方案順序無關緊要（解{2，2，3}和{3，2，2}是相等的）。

請注意，最終組合不需要是一個集合，因爲它可以包含重複項。

實施例：集{2,3,5} 薩姆10

結果： {2,2，2，2，2}，{2,2，3,3}，{2， 3，5}，{5，5}

我已經看過子集合問題以及幣改變問題，但無法調整它們以適應我的需要。我對動態編程並不是很熟悉，所以它可能是可行的，但我無法弄清楚。

由於我正在處理相當大的元素集合（大約50），所以預計算所有集合都不是一個選項，因爲它需要很長時間。從子集合表中提取不同解決方案的方法將是可取的（如果可能的話）。

任何意見，提示或示例代碼，將不勝感激！

來源

2017-01-23 Dzik

可能的複製[與總和薩姆數組值等於X]（HTTP：//計算器。com/questions/595707/sum-array-values-with-sum-equals-x） – TiMr

@TiMr對不起，但那個答案不是我正在尋找的。每個結果都是一個集合（沒有重複），但是我正在尋找一種方法來查找所有解決方案，包括那些具有多個相同元素的解決方案，就像我提供的示例一樣。 – Dzik

與subset-sum（它允許集合或多集合）或無界揹包沒有什麼不同。 –

-1

解決方案的複雜性：

時間：O（N * M）
存儲器：O（M），

其中M是總和的值，n被設定尺寸

int numberOfSums(Set<Integer> values, int sum) { 
    // sumCount[i] -> number of ways to get sum == i 
    int sumCount[] = new int[sum+1]; 
    sumCount[0] = 1; 
    for(int v : values) { 
     for(int i=0; i<=sum-v; ++i) 
      sumCount[i+v] += sumCount[i]; 
    } 
    return sumCount[sum]; 
}

來源

2017-01-23 14:56:23 arvaladze

這是一個計算答案的Haskell函數：

partitions 0 xs = [[]] 
partitions _ [] = [] 
partitions n ([email protected](x:xs)) | n < 0 = [] 
          | otherwise = (map (x:) (partitions (n-x) xxs)) ++ partitions n xs

實例：

*Main> partitions 1 [1] 
[[1]] 
*Main> partitions 5 [1..5] 
[[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]] 
*Main> length $ partitions 10 [1..10] 
42 
*Main> length $ partitions 20 [1..20] 
627 
*Main> length $ partitions 40 [1..40] 
37338 
*Main> partitions 10 [1,2,4] 
[[1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2],[1,1,1,1,1,1,2,2],[1,1,1,1,1,1,4],[1,1,1,1,2,2,2],[1,1,1,1,2,4],[1,1,2,2,2,2],[1,1,2,2,4],[1,1,4,4],[2,2,2,2,2],[2,2,2,4],[2,4,4]]

Semi-live demo

來源

2017-01-23 17:33:19

這被稱爲Change-making problem和處於dynamic programming一個典型例子。

一些早期的答案已計算的總計數解決方案，而這個問題已經問了枚舉可能的解決方案。

你還沒有用語言標記你的問題，所以這裏是一個Python實現。通過使用您的語言的「bag」數據類型將其適應於任何您需要的語言（n.b. Counter是Python的「包」）。

from collections import Counter 

def ways(total, coins): 
    ways = [[Counter()]] + [[] for _ in range(total)] 
    for coin in coins: 
     for i in range(coin, total + 1): 
      ways[i] += [way + Counter({coin: 1}) for way in ways[i-coin]] 
    return ways[total]

輸出數據類型是行李列表。用於打印演示他們使用：的

>>> from __future__ import print_function # for Python 2 compatibility 
>>> for way in ways(total=10, coins=(2,3,5)): 
...  coins = (coin for coin,count in way.items() for _ in range(count)) 
...  print(*coins) 
... 
2 2 2 2 2 
2 2 3 3 
2 3 5 
5 5

來源

2017-01-23 17:43:44 wim

查找給定的一組整數的總和達到給定總和的所有組合

回答

相關問題