Ruby每周一测 - 找零钱

38, [20, 19, 1]没有bug #[20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
我只想出了和seairy同样的方法，这种方法可读性看来还是很好的。

谢谢庄兄指出错误，正在修正。。。
目前我的修正版和你的递归算法都存在一个问题，就是当钱总数比较大，可用零钱集合比较多的时候，效率都相当低。
比如：
make_change1(380,[25, 10, 5, 1])
还值得好好优化优化。。。琢磨中。。。
（话说回来，要找380美分的零钱，不能全给钢镚吧？呵呵）

taro同学，38, [20, 19, 1]最优结果应该是[19,19]

def make_change(amount, coins = [25, 10, 5, 1])
  return [amount] if coins.include?(amount)
  temp_coins=coins.select {|x| x <= amount}
  max_coin=temp_coins[0]
  first_coins=temp_coins.select {|x| x*2>max_coin}
  min_one_coin=nil
  min_coins=Array.new(amount)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin})
    if other_coins && min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
    if other_coins && min_coins.size<other_coins.size
      break
    end
  end
  min_one_coin ? [min_one_coin]+min_coins : nil
end

效率提升版，计算(380,[20,19,1])大约是上一个版本的30倍。

庄兄，有bug：
make_change(30,[21,10,1])

的确会有bug

我再想想

呵呵，以后一定多做实验在发言……

嘿嘿，这个有意思。。。

做了个解法，看起来还不错。。

似乎无解的时候效率比较差。。。大家给评评。

def make_change(amount, coins = [25, 10, 5, 1]) 
  res_size = -1
  result = nil
  
  coins.each do |c|
    res = []
    cnt = (amount/c)
    
    next if res_size!=-1 and cnt >= res_size

    cnt.times do
      res << c
    end

    if (r=amount % c) == 0 #刚好除尽。
      if res_size==-1 or res_size>res.size
        result = res.clone
        res_size = result.size
      end
      next
    end
    
    remain_coins =  coins.select{|c| c<=r} #还有比余数小的零钱不？
    return nil if remain_coins.size==0
    
    
    #还有比余数小的零钱哦。
    tmp_res = make_change(r,remain_coins)
    next if (tmp_res.nil? or tmp_res.size ==0) 
    temp_rs = res.size + tmp_res.size
    
    if(res_size==-1 or temp_rs<res_size)
      res_size = temp_rs
      res << tmp_res
      result = res.clone
    end
  end
  return result.flatten
end

p make_change(14,[10,7,2])
p make_change(38,[20,19,17,1])
p make_change(38,[20,17,3])
p make_change(39)
p make_change(14,[10,5,1])
p make_change(380,[20,19,1])
p make_change(40,[39,10,1])

结果：
[7, 7]
[19, 19]
nil
[25, 10, 1, 1, 1, 1]
[10, 1, 1, 1, 1]
[20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20]
[39, 1]

刚学ruby 看了一楼的 代码 之后 仿照他的 也写了一段 请高手帮我看看对不对：~

def make_change(amount, coins)  
already = []
index=0
mc(amount,coins,already,index);
print already.join("   ")
end
def mc(amount, coins,already,index)  
  if(amount<coins[coins.size-1]) 
    return already;
  end
  if(index<coins.size-1)
    if(coins[index]<coins[index+1]*2)
      if amount<(coins[index]+coins[index+1])
          index+=1
          mc(amount,coins,already,index)
      else
        already[already.size]=coins[index]
        amount=amount-coins[index]
        mc(amount,coins,already,index)
      end
    else
      if amount<coins[index]
          index+=1
          mc(amount,coins,already,index)
      else
        already[already.size]=coins[index]
        amount=amount-coins[index]
        mc(amount,coins,already,index)
      end
    end
  else
    if amount<coins[index]
        index+=1
        mc(amount,coins,already,index)
    else
      already[already.size]=coins[index]
      amount=amount-coins[index]
      mc(amount,coins,already,index)
    end
  end
  return already;
end

哈哈，总算给我找到一个bug
p make_change(5,[3,2])  ==> [3,2]
p make_change(5,[4,3,2])  ==> nil