【贪心策略】硬币问题-蒲公英云

【贪心策略】硬币问题

问题描述：

有vi=1元、5元、10元、50元、100元、500元的硬币c1、c2、c3、c4、c5枚。若用这些硬币来凑出A元，最少需要多少枚硬币？

贪心策略：

初始化numOfCoins=0，若A>0

每一次都优先挑金额最大的硬币 i

  若该硬币金额大于A，则挑金额次之的硬币
  若该硬币金额小于A & 该硬币的剩余数量 ci 不为0，则A=A-vi，numOfCoins++

代码实现：

// 贪心算法————硬币问题
public class CoinsTest {
    public static void main(String[] args) {
        int[] v = {0, 1, 5, 10, 50, 100, 500}; // 硬币的金额
        int[] c = {0, 3, 2, 1, 3, 0, 2}; // 硬币的个数
        int A = 620; // 数额
        int numOfCoins = 0;          // 记录总共需要的硬币个数
        int[] flag = new int[7];  // 记录对应的硬币被选择的次数 
        for (int i=6; i>0; i--) {
            // A == 0 
            if (A == 0) {  // 代码出口
                break;
            }
            // A > 0
            while (c[i] > 0) {
                if (v[i] > A) {
                    break;
                } else {
                    A -= v[i];
                    c[i]--;
                    numOfCoins++;
                    flag[i]++;
                }
            }
        }
        //打印方案选择的硬币个数
        System.out.println("要凑出A元，至少需要"+ numOfCoins +"枚硬币");
        //打印方案
        System.out.print("所选择的硬币为：");
        for (int i=6; i>0; i--) {
            while (flag[i] > 0) {
                System.out.print(v[i]+"\t");
                flag[i]--;
            }
        }
    }
}