分硬币问题(贪心)

import java.util.Scanner;

/*硬币问题
 * 有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。
 * 现在要用这些硬币来支付A元，最少需要多少枚硬币？假定本题存在一中支付方案。
 * 限制条件：
 * 0≤C1,C5,C10,C50,C100,C500≤10的9次方
 * 0≤A≤10的9次方
 * 
 * 输入
 * C1=3,C5=2,C10=1,C50=3,C100=0,C500=2,A=620;
 * 输出：
 * 6(500元硬币1枚，50元硬币2枚，10元硬币1枚，5元硬币2枚，合集6枚)
 * */
public class CoinMax
{
	public static int[] C = new int[6];
	public static int[] V = new int[] {1, 5, 10, 50, 100, 500};//硬币的面值
	public static int A;
	public static void main(String[] args)
	{
		Scanner cin = new Scanner(System.in);
		System.out.println("请依次输入C1---C500的枚数：");
		for (int i = 0; i < 6; ++i)
		{
			C[i] = cin.nextInt();
		}
		System.out.println("支付A元：");
		A = cin.nextInt();
		cin.close();
		solve();
	}
	public static void solve()
	{
		int ans = 0;
		for (int i = 5; i >= 0; --i)
		{
			int t = Math.min(A / V[i], C[i]);
			++ans;
			if (t != 0)
				System.out.print(V[i] + "元" + t + "枚 , ");
			A -= t * V[i];
		}
		System.out.println("共" + ans + "枚");
	}
}