贪心算法训练 硬币找零

Ⅰ 题目 硬币找零

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张.
现在要用这些钱来支付K元,至少要用多少张纸币?

Ⅱ 大体思路

主要练习贪心算法。贪心算法的核心是 无后效性,即 当前的选择既不改变之前的状态,也不会影响以后的状态。
在硬币找零中,每一次按照最大的货币的值给他。
整体的思路如下: 
    ① 定义一个数组模拟当前手中的现金;
    ② 数组的初始化,价值和对应剩余的数目;
    ③ 输入一个数 K 表示要找零钱的总数;
    ④ 返回结果,如果找回 输出 yes
                否则输出 no。

Ⅲ 部分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 贪心核心算法
* 当前剩余的货币 = 当前的货币- 已经找零的货币
* 当前找零货币的剩余张数 = 当前的零钱货币的张数 - 已经找零的货币的张数
* 已经找零的货币的张数 = min(当前的货币/当前的零钱的价值,当前货币的张数)
* */
private static String greedReCoin(int[][] arrCoin, int K) {
int count = 0;
for(int i = arrCoin.length-1; i >=1;i--){
int number = Math.min(K/arrCoin[i][0],arrCoin[i][1]);
K -= number*arrCoin[i][0];
arrCoin[i][1] -= number;
count += number;
if(K == 0) return"yes 至少" + count + "张";
}
return "no";
}

Ⅳ 全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;
public class ReCoin {
private static Scanner sc;
public static void main(String[] args) {
sc = new Scanner(System.in);
int[][] arrCoin = new int[8][2];//使用二维数组模拟 [价值][张数]
for(int i = 1; i < arrCoin.length;i++){
arrCoin[i][0] = sc.nextInt();
arrCoin[i][1] = sc.nextInt();
}
int K = sc.nextInt();
String result = greedReCoin(arrCoin,K);
System.out.println(result);
}
/**
* 贪心核心算法
* 当前剩余的货币 = 当前的货币- 已经找零的货币
* 当前找零货币的剩余张数 = 当前的零钱货币的张数 - 已经找零的货币的张数
* 已经找零的货币的张数 = min(当前的货币/当前的零钱的价值,当前货币的张数)
* */
private static String greedReCoin(int[][] arrCoin, int K) {
int count = 0;
for(int i = arrCoin.length-1; i >=1;i--){
int number = Math.min(K/arrCoin[i][0],arrCoin[i][1]);
K -= number*arrCoin[i][0];
arrCoin[i][1] -= number;
count += number;
if(K == 0) return"yes 至少" + count + "张";
}
return "no";
}
}