作者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