问题
有11,5,1 三种币值 要凑15块钱 问题：求 钱的张数最小贪婪法
1. 贪婪法：先用最大的，然后依次，最后用1块做填补 - 如果W比任何一张币值大，且一定可以补够，比如有1块就可以 - 特例： 1. w没有币值大 2. 比如：11,5,3 选11 就凑不够15块,也就是说 先选最大币值未必能拼够 3. 贪婪算法 一般情况下都不是最优解， 只有大面值可以覆盖所有小面值，这种方案才能得到最优解，比如：100,50,10,5,1就可以动态规划法
动态规划方法 拼凑15块钱，需要最小的钱的张数，称为F(15) 那么： F(15) = Min( F(15-11) + 1, F(15-5) + 1, F(15-1) + 1 ) = Min( F(4) , F(10) , F(14) ) + 1 F(10) = Min( F(10-11) + 1, F(10-5) + 1, F(10-1) + 1) = Min( F(-1) , F(5) , F(9) )+ 1 = Min( F(5) , F(9) )+ 1 = Min( 1 , F(9) )+ 1 说明： F(4)+1 : 用了一张11块币值，剩余需要凑4块的钱的张数 F(5) ： 凑跟币值一样的钱数，当然是直接使用一张5块的就算完事 F(10): 凑10块 可以选：5，也可以选1块。 这个还按照贪婪从大到小，当然还需要比对。 - 优化点：咱看到5的下一级只需要取5块，2张就完事。 就没必要：5+1+1+1+1+1 直到最后 类似问题： 1. 第n个元素的值：F(n) = F(n-2) + (n-1) - n=1,2为2,3 2. 导航问题：假设A-Z导航，A后两条出口B，C - Min(a,z) = Min( (A-B) + Min(B,Z) ,(A-C) + Min(C,Z) ) 编码：递归，这类问题用递归 跟问题分析很对应代码(Java)
@Test public void test1(){ // 有11,5,1 三种币值 int [] currencyValues =new int[]{11,5,1}; // 要凑15块钱 int w = 15; // 问题：求 钱的张数最小 Solution Solution = new Solution(); Assert.assertEquals(3, Solution.miniNumberOfMoney(currencyValues,w)); Assert.assertEquals(2, Solution.miniNumberOfMoney(new int[]{11,5,1},6)); // 这种就是无解场景 Assert.assertEquals(2, Solution.miniNumberOfMoney(new int[]{11,5,2},6)); } /** * 动态规划方法 * 拼凑15块钱，需要最小的钱的张数，称为F(15) * 那么： * F(15) = Min( F(15-11) + 1, F(15-5) + 1, F(15-1) + 1 ) * = Min( F(4) , F(10) , F(14) ) + 1 * * F(10) = Min( F(10-11) + 1, F(10-5) + 1, F(10-1) + 1) * = Min( F(-1) , F(5) , F(9) )+ 1 * = Min( F(5) , F(9) )+ 1 * = Min( 1 , F(9) )+ 1 * 说明： * F(4)+1 : 用了一张11块币值，剩余需要凑4块的钱的张数 * F(5) ： 凑跟币值一样的钱数，当然是直接使用一张5块的就算完事 * F(10): 凑10块 可以选：5，也可以选1块。 这个还按照贪婪从大到小，当然还需要比对。 * - 优化点：咱看到5的下一级只需要取5块，2张就完事。 就没必要：5+1+1+1+1+1 直到最后 * * 类似问题： * 1. 第n个元素的值：F(n) = F(n-2) + (n-1) * - n=1,2为2,3 * 2. 导航问题：假设A-Z导航，A后两条出口B，C * - Min(a,z) = Min( (A-B) + Min(B,Z) ,(A-C) + Min(C,Z) ) * * 编码：递归，这类问题用递归 跟问题分析很对应 */ class Solution { public int miniNumberOfMoney(int[] moneys,int w) { int miniNum = Integer.MAX_VALUE; int tempMiniNum = 0; for(int i = 0 ; i < moneys.length ; i++){ if(moneys[i] > w){ // 拼凑的钱直接比当前币值小，比如拼凑99块，100面值就直接过了。 continue; }else if(moneys[i] == w){ // 拼凑的钱 跟 比当前币值相等，那么最新少的就是一张 tempMiniNum = 1; }else if(moneys[i] < w){ tempMiniNum = miniNumberOfMoney(moneys,w - moneys[i]) + 1; } // 如果这种币值的钱张数 比较少就记录 if(tempMiniNum < miniNum){ miniNum = tempMiniNum; } } return miniNum; } }end
