求一算法

Question

如基数为10,20,30,50,100假如我传110,120,300,140怎样才能快速的找到最优路径:100+10 =110100+20 =120100+100+100 =300100+20+20 =140 或 100+10+30 =140
请算法高手给指条明路.谢谢!~

Answer 1

第一个集合做乘法的笛卡尔集存到一个hashtable里，传入第二组数通过hash表来找算法吧？

Answer 2

基数 先排序 变成 有序 数组传递参数时 从 大到小遍历数组 判断 与 传递参数 的大小eg: 110>100?  满足的话 ，做差 记录 下标 与 差 (10), 判断差是否为0 不为0 继续 从 大到小遍历数组 判断 与 传递参数 的大小找到 10  做差 记录下标  。 这时 已经满足条件 找到了 100 与 10难点 是 需要回溯 假设 基数为 10,20,30,50,101 时首先 找到 101 ，之后 循环数组到结束 也没满足 需要回溯  
根据下标  取下标 减一 开始 ，直至 到0

Answer 3

100+10 =110100+20 =120
------------------------------------------
110，120这两个  可以通过 预存 基数的 两两组合 实现 快速匹配
100+100+100 =300100+20+20 =140 或 100+10+30 =140 
-----------------------------------------------
两两 组合 没办法快速匹配的时候 ，还是需要挨个判断的也可以利用两两组合 后的结果 进行比较 ，同理 将两两组合 后的结果 变成有序集合 
是key,value 的形式 key 为两两组合的结果，value 为 两个基数的下标 "下标,下标"eg: 20,   30,    40,      50,      ...        120,     130,       150,        200  
    0,0   0,1    1,1      1,2      ...        1,4      2,4        3,4         4,4然后 与 传递的参数比较 目的 就是你预先 替计算机做一些事情