【蓝桥云课】找零问题

蓝桥云课】找零问题"/>

【蓝桥云课】找零问题

问题描述：有币种1、2、4、5、10若干张，找零n元，输出找零方案。

方法一：枚举所有方案

程序代码：

//枚举
public static void meiju(int n) {int count = 1;//方案数for (int i = 0; i <= n/1; i++) {//穷举1元的for (int j = 0; j <= n/2; j++) {//穷举2元的for (int k = 0; k <= n/4; k++) {//穷举4元的for(int x = 0; x <= n/5; x++) {//穷举5元的for(int y = 0; y <= n/10; y++) {//穷举10元的if(i*1+j*2+k*4+x*5+y*10 == n) {System.out.printf("方案%2dth:{1:%2d}{2:%2d}{4:%2d}{5:%2d}{10:%2d},张数:%2d\n",count++,i,j,k,x,y,i+j+k+x+y);}}}}}}
}

以n=8为例：

方案 1th:{1: 0}{2: 0}{4: 2}{5: 0}{10: 0},张数: 2
方案 2th:{1: 0}{2: 2}{4: 1}{5: 0}{10: 0},张数: 3
方案 3th:{1: 0}{2: 4}{4: 0}{5: 0}{10: 0},张数: 4
方案 4th:{1: 1}{2: 1}{4: 0}{5: 1}{10: 0},张数: 3
方案 5th:{1: 2}{2: 1}{4: 1}{5: 0}{10: 0},张数: 4
方案 6th:{1: 2}{2: 3}{4: 0}{5: 0}{10: 0},张数: 5
方案 7th:{1: 3}{2: 0}{4: 0}{5: 1}{10: 0},张数: 4
方案 8th:{1: 4}{2: 0}{4: 1}{5: 0}{10: 0},张数: 5
方案 9th:{1: 4}{2: 2}{4: 0}{5: 0}{10: 0},张数: 6
方案10th:{1: 6}{2: 1}{4: 0}{5: 0}{10: 0},张数: 7
方案11th:{1: 8}{2: 0}{4: 0}{5: 0}{10: 0},张数: 8

方法二：贪心策略，每次都用可找币种的最大面值去找

//贪心 n元 (n-可以找到的最大面值) +1，从大面值到小面值试探
public static void greedy(int n) {int[] money = {10,5,4,2,1};int i=0;//下标表示目前用money数组的哪一个币种找零钱，最开始从10元开始试探int[] num = new int[money.length];while(n > 0) {//只要找钱的过程没有结束，继续//n>当前面值money[i]if(n>=money[i]) {int zs = n / money[i];n = n - zs * money[i];num[i] = num[i] + zs;} else {i++;}}for(int j=0;j<num.length;j++) {if(num[j]>0)System.out.printf("面值%2d:张数%2d ",money[j],num[j]);}
}

以n=8为例：

面值 5:张数 1 面值 2:张数 1 面值 1:张数 1 

方法三：动态规划

c [ i ] [ j ] c[i][j] c[i][j]表示第 i 种币值去找 j 元需要的最少张数

c [ i ] [ j ] = m i n c[i][j] = min c[i][j]=min{c[i-1][j], c[i][j-money[i]]+1}

//动态规划 c[i][j] = min{c[i-1][j],c[i][j-money[i]]+1}
public static void dpchangeMoney(int n) {int[] money = {0,1,2,4,5,10};int[][] c = new int[money.length][n+1];for (int i = 0; i <= n; i++) {c[0][i] = 99999;}for (int i = 0; i < money.length; i++) {c[i][0] = 0;}for (int coin = 1; coin < money.length; coin++) {for (int change = 1; change <= n; change++) {if(money[coin] > change) {c[coin][change] = c[coin-1][change];} else {c[coin][change] = Math.min(c[coin-1][change], c[coin][change-money[coin]]+1);}}}for(int[] x:c) System.out.println(Arrays.toString(x));System.out.println(c[money.length-1][n]);
}

以n=8为例：

[0, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 1, 2, 2, 3, 3, 4, 4]
[0, 1, 1, 2, 1, 2, 2, 3, 2]
[0, 1, 1, 2, 1, 1, 2, 2, 2]
[0, 1, 1, 2, 1, 1, 2, 2, 2]
2