本文共 920 字，大约阅读时间需要 3 分钟。

问题描述：

有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]--;			}		}	}}

 运行结果：

转载地址：http://lbnii.baihongyu.com/