Ruby每周一测 - 找零钱

to：solo9c

p make_change(38,[20,19,17,1])

你的结果是19,17,1,1；而不是19,19

哈哈。多谢多谢。。。
24行：
return nil if remain_coins.size==0
改为
next if remain_coins.size==0

返回的时候：
return result.flatten
改为：
return nil unless result
return result.flatten

哈哈LS诸位都是贪心鬼阿.但是很不幸的告诉各位,找零钱等价背包问题,如果要找全局最优解的话就不要往贪心上化功夫了.贪心找不到全局最优解,贪心法的最优子结构性质需要根据硬币面值和初次贪心选择来定,特定组合的面值或者特定选择顺序可以得到最优解一般情况下是局部最优解!还是用动态规划靠谱一点.通项也不是很难得了 C(t)=min{1+C(t-di),di<=t,1<=i<=n};C(t)是t元时的最小值,n是硬币种类,di是硬币面值.复杂度o(n^2).

直觉当然很重要,但是可以说大量的算法问题都是违犯直觉的赫赫.

庄兄，最好把传入的coins参数先做个从大到小的排序，否则你的程序会n慢哦，比如make_change(400,[1,2,5,10,20,50,100])

写了个解法,不用递归,采用类似枚举的算法（脑子不够灵光了呵呵）,不能算太大哦（算10000那是花了n长时间，相比老庄的算法差得远哈哈）

def make_change(to_charge_money,charges=[1,2,5,10,20,50,100])
  all_charge_results=func1(charges,to_charge_money)
  return all_charge_results[to_charge_money-1]
end

def func1(c_array,num)
  c_map=[]
  (1..num).each{|e|
    #can charge?
    b=c_array.find_all{|x| x<=e}
    if b.size>0 #has small charges
      gotit=b.find{|x| x==e}
      if gotit.nil?        
        c_map[e-1]=best_charge(e,c_map)
      else
        c_map[e-1]=[e] #charge directly
      end
    else #has no small charges
      c_map[e-1]=nil
    end
  }
  return c_map
end

def best_charge(be_charged,c_map)
  loop_num=be_charged/2
  charge_num=[]
  charge_option={}
  mem=0
  (0..(loop_num-1)).each{|i|
    sub_charge1=c_map[i]
    sub_charge2=c_map[be_charged-2-i]
    if sub_charge1!=nil && sub_charge2!=nil
      num=sub_charge1.size+sub_charge2.size
      charge_num[mem]=num
      charge_option.store(num,sub_charge1 + sub_charge2)
      mem=mem+1
    end
  }
  if charge_num.size>0
    min_num=(charge_num.sort)[0]
    return charge_option[min_num]
  else
    return nil
  end
end

你看题不认真。

我直觉上也认为，这题目不能通过“剪枝”来优化。不过，麻烦写一个code来看看吧，光看你的公式，不明白的。

sorry，我前面描述得不是很好。完整的说，目前我的算法思路应该是贪心+穷举。因为可用零钱集合不是很大，所以穷举的代价不会太高。当然，如果钱数很大，穷举肯定影响性能，不过可以通过一些其他手段优化，如果，查找某种方法，一旦发现零钱个数超过目前的最优解，则break。。。等等。。暂时还没实现完。。完了再贴上代码。
至于动态规划法。。。实在惭愧，都还给大学算法老师了。还是用熟悉点的方法吧~空了再研究研究。。。

这才是真正的高手。。。



就是我前面的那个实现。。。

依靠回溯的话,请小心搜索的复杂度可能是o(n!)哦