问题:
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？
public class Main {
static int count = 11; // 计算11的最少由多少硬币组成
static int[] coins = { 1, 3, 5 }; // 共有面值1，3，5
public static void main(String[] args) {
int[] result = new int[count + 1];// 声明12个位置的数组，每个item存储该值最少可以由几枚硬币组成
for (int i = 1; i <= count; i++) {// 计算 1-count,每个最少由几枚硬币组成
int best = Integer.MAX_VALUE;
for (int j = 0; j < coins.length; j++) {//遍历所有硬币
int coin = coins[j];
if (i - coin < 0) {
break;
} else if (best > 1 + result[i - coin]) {
best = 1 + result[i - coin];
}
}
if (best != Integer.MAX_VALUE) {
result[i] = best;
}
}
for (int i : result) {//输出结果
System.out.println(i);
}
}
}
面值0：coin=1>0, break;
面值1：
- coin=1==1,best=result[1-1]+1=0+1=1=[c1];
- coin=3>1,break;
面值2：
- coin=1<2,best=result[2-1]+1=1+1=2=[c1+c1];
- coin=3>2,break;
面值3：
- coin=1<3,best=result[3-1]+1=2+1=3=[c1+c1+c1];
- coin=3==3,best=result[3-3]+1=1=[c3];
- coin=5>3,break;
面值4：
- coin=1<4, best=result[4-1]+1=1+1=2=[c3+c1]
- coin=3<4, best = result[4-3] +1 =1+1=2=[c1+c3]
- coin=5>4,break
面值5：
- coin=1<5, best=result[5-1]+1=2+1=2=[c3+c1+c1]
- coin=3<5, best = result[5-3] +1 =2+1=3=[c1+c1+c3]
- coin=5==5,best=result[5-5]+1=0+1=1=[c5]
……
result[i] = min{result[i-C1]+1,result[i-C2]+1,result[i-C2]+1}
算法导论(网易公开课)
