贪婪算法

钱币找零问题
这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。

 public Map change(int[] a,int[] count,int target){
        Map<Integer, Integer> map=new HashMap<Integer, Integer>();
        for(int i=a.length-1;i>=0;i--){
            if(a[i]>target){
                continue;
            }
            while(target>0) {
                if(a[i]>target){
                    break;
                }
                if(!map.containsKey(a[i])){
                    map.put(a[i], 1);
                    target=target-a[i];

                }
                else{
                    if(map.get(a[i])<count[i]){
                        map.put(a[i], map.get(a[i])+1);
                        target=target-a[i];
                    }
                    else{
                        break;
                    }
                }
            }
        }
        return map;
        
    }

  public static void main(String[] args) {
        //人民币面值集合
        int[] values = { 1, 2, 5, 10, 20, 50, 100 };
        //各种面值对应数量集合
        int[] counts = { 3, 1, 2, 1, 1, 3, 5 };
        //求442元人民币需各种面值多少张
        int[] num = change(442, values, counts);
        print(num, values);
    }