[問題] 求某數是由數列中的哪些數字加總?
各位大大好
我上一個發問的問題-「數字組合可能性」，其實是為了解決現在這個問題
目前已經寫的出來數列的冪集合了，感謝回答的大大們
但是現在現實上的情況可能不適用於冪集合，因此再來請教
是這樣的
現在要寫一個程式，有一個數字及一數列，要求這一數字是由數列中的哪些數字加總的
非單一答案，所以要求顯示各種組合性
舉個例子： 90 是由 {30, 20, 50, 40, 60} 這些數字中的哪些數字加總起來的
可能組合性有..
組合一： 50 + 40 = 90
組合二： 30 + 60 = 90
組合三： 30 + 20 + 40 = 90
這個程式就是像這樣，要讓使用者輸入total和數列，程式再跑出所有組合情況
原本我的想法是用冪集合展開數列中所有數字的組合可能性，
讓各個組合做加總，加總後再去判斷哪個數字等於user輸入的total
等於total的那個組合就是答案了
想說這樣絕對不會miss，因為所有的組合性都會跑過、檢查過，正確性也有
但問題來了，這方式只適用數列個數很小的時候
當數列個數大於20的時候，程式就開始跑很久了
我算過當個數是30時，組合性有10億，每種組合要跑過的話，迴圈至少要跑10億圈
問過user，他們最多有可能到50個數字
所以想請教，有沒有什麼方式或演算法可以解決?
謝謝
另外，我問過數學系的朋友，他的回答也跟我的想法一樣
（就是冪集合的方式，一組一組檢查），可是這樣個數多時會很久
也想過「找零錢問題」
像是 http://tw.myblog.yahoo.com/dust512/article?mid=-2&prev=14&l=a&fid=5
可是「找零錢問題」的情況和我的問題不太一樣，「找零錢問題」的零錢面額可以有
很多個，例如：10元硬碟*n
而我的情況是，同一個組合裡，同一個數字只能出現一次
所以和「找零錢問題」不太一樣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.32.180
→
06/05 11:19, , 1F
06/05 11:19, 1F
→
06/05 11:19, , 2F
06/05 11:19, 2F
→
06/05 11:21, , 3F
06/05 11:21, 3F
→
06/05 11:21, , 4F
06/05 11:21, 4F
→
06/05 11:22, , 5F
06/05 11:22, 5F
→
06/05 11:22, , 6F
06/05 11:22, 6F
→
06/05 11:27, , 7F
06/05 11:27, 7F
→
06/05 11:28, , 8F
06/05 11:28, 8F
→
06/05 12:37, , 9F
06/05 12:37, 9F
→
06/05 17:51, , 10F
06/05 17:51, 10F
→
06/05 17:57, , 11F
06/05 17:57, 11F
→
06/05 20:28, , 12F
06/05 20:28, 12F
→
06/05 20:28, , 13F
06/05 20:28, 13F
推
06/05 20:49, , 14F
06/05 20:49, 14F
→
06/07 15:19, , 15F
06/07 15:19, 15F
→
06/07 15:40, , 16F
06/07 15:40, 16F
→
06/13 22:05, , 17F
06/13 22:05, 17F
→
06/13 22:06, , 18F
06/13 22:06, 18F