作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] 數字加總問題
時間Mon Jun 1 01:00:05 2009
※ 引述《jinmin88 ()》之銘言：
: 最近工作上碰到一個棘手的問題，想請問版上高手是否有較好的演算法可以解決
: 譬如說DB中存有一些數字集合 S={ 11, 43, 41, 49, 91 }
: 今天我手邊會有一組輸入,如102
: 我希望輸入102後,程式可以告訴我集合中哪些組合可以加總後變成102
: 如 S'={11,91}為此例的解 又如輸入95則答案為 {11,43,41} ... etc
: 當然可能會有一組以上的解,直覺上我如果用暴力法可能會算不完
: 因為實際上的樣本可能有一千以上個數字集合(實際上為訂單集合),
: 請問除了暴力法之外,有沒有比較可能算的出來的辦法？謝謝
將輸入的數字剖半 => 102 / 2 = 51
根據 51, 資料分成小集合是 {11, 43, 41, 49}, 大集合是 {91},
要想的就是小集合的哪些和大集合的哪些加起來是 102.
不管是再用暴力處理,或是再用其他有效的方法,都可以省一些時間.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.226.220
1F：推 CharlesB:小集合也有可能加起來等於51 06/01 09:02
2F：→ yauhh:我以為是二個數自相加而已 06/01 12:07
3F：→ prettyfaces:好有趣的工作‥‥我的工作不常用得上數學 10/24 16:58
4F：→ prettyfaces:一時想不到什麼好的heuristic 拍謝 10/24 17:00