0
Posted on Friday, October 20, 2017 by 醉·醉·鱼 and labeled under
给指定的硬币类型,用最少的硬币个数,找出指定的amount。比如,现在有[2, 5, 10, 20, 50]这几种硬币,找出21块钱出来。

这个其实是算法导论里面动态规划。无意间,发现还有其他的实现方法。记录下来。

首先是动态规划。原来是,21块钱,可以拆分成19+2, 16+5, 11+10, 1+20。19又可以继续拆分成17+2, 14+5, 9+10。以此类推下去。里面有个技术点就是,还可以用block去定义Hash,厉害了。代码如下:

 def change(coins, amount, results = [])
    return [] if amount == 0

    coins.sort! { |a, b| a <=> b }

    optimal_change = Hash.new do |hash, key|

      if key < coins.min
        hash[key] = []
      elsif coins.include?(key)
        hash[key] = [key]
      else
        hash[key] = coins
            .reject { |coin| coin > key }
            .map { |coin| [coin] + hash[key - coin] }
            .reject { |change| change.inject(&:+) != key }
            .min { |a, b| a.size <=> b.size } || []
      end

      puts hash
      hash[key]
    end

    optimal_change[amount].empty? ? -1 : optimal_change[amount].sort
end



另外一种方法是,创建一个数组,从1到amount,然后逐一用coin去替代,最后一个就是amount对应的coin了。


  def change(coins, total_change)
    return -1 if total_change < 0 || coins.any? { |x| x < 1 }
    m = [[]] + [nil] * total_change
    coins.size
         .times
         .to_a
         .product((1..m.size - 1).to_a)
         .each { |c, t|
           if coins[c] == t
             m[t] = [coins[c]]
           else
             (1..t - 1).select { |t2| coins[c] + t2 == t }
                       .reject { |t2| m[t2].nil? }
                       .each { |t2| 
                         m[t] = m[t2] + [coins[c]] if m[t].nil? || m[t2].size + 1 < m[t].size 
                       }
           end
         }
    m[-1].nil? ? -1 : m[-1]
  end
0
Responses to ... 用最少硬币找零问题

Post a Comment