首页 > 代码库 > 硬币找钱问题,求所有可能解决方案数目,最少的钱币数目,每种钱币用多少张
硬币找钱问题,求所有可能解决方案数目,最少的钱币数目,每种钱币用多少张
【题目简介】
现存在一堆面值为 V1、V2、V3 … 个单位的硬币,一共有多少种找钱方法可以找出总值为 T 个单位的零钱?最少需要多少张钱币?在最少钱币数目找钱的条件下,每种钱币使用的次数是多少?假设这一堆面值分别为 1,2,3 元,需要找出总值 T 为 4 元的零钱。很明显,一共有4中找钱方法:1 + 1 + 1 + 1, 2 + 2, 1 + 3, 2 + 2 + 1 + 1;最少需要两张钱币,可能为 3 + 1或者2 + 2.当存在多种情况时,只需要输出其中一种。
【题目参数】
int coinsUsed[i];//用来保存总共找i元钱,需要最少的钱币张数 int coinTimes[i][j];//用来保存总共找i元钱,需要最少钱币张数时,第j中钱币的使用次数 int solutions[i];//用来保存总共找i元钱,所有的可能解决方案的数目 int[] coinValue = http://www.mamicode.com/new int[] { 3, 2, 1 }; //保存用于保存钱币面值的数组>
【题目解决方案】动态递归思想
一、求解一共有多少种解决方案
假设这一堆面值分别为 1,2,3 元,需要找出总值 T 为 4 元的零钱。很明显,一共有4中找钱方法:1 + 1 + 1 + 1, 2 + 2, 1 + 3, 2 + 2 + 1 + 1
解决方案:
主要公式solutions[i] = solutions[i] + solutions[i - values[kind]]
1.只允许使用第一种钱币,则
solutions[1] = solutions[1] + solutions[0] = 1,即 1 = 1 + 0
solutions[2] = solutions[2] + solutions[1] = 1,即 2 = 1 + 1
solutions[3] = solutions[3] + solutions[2] = 1,即 3 = 1 + 1 + 1
solutions[4] = solutions[4] + solutions[3] = 1,即 4 = 1 + 1 + 1 + 1
2.允许使用两种钱币,第一种和第二种,则
solutions[2] = solutions[2] + solutions[0] = 2,即在1基础上,2 = 2 + 0
solutions[3] = solutions[3] + solutions[1] = 2,即在1基础上,3 = 1 + 2
solutions[4] = solutions[4] + solutions[2] = 3,即在1基础上,4 = 2 + 2 = 2 + 0 +2 = 1 + 1 + 2
3.允许使用三种钱币,第一种、第二种和第三种
solutions[3] = solutions[3] + solutions[0] = 3,即在1基础上,3 = 0 + 3
solutions[4] = solutions[4] + solutions[1] = 4,即在1基础上,4 =1 + 3
二、求解最少需要几张钱币
假设coinsUsed[i]在j < i时coinsUsed[j]已经算出来了,那么算coinsUsed[i]的时候,最好的情况下是在前面的基础上再增加一张钱币,所以
coinsUsed[i] = min(coinsUsed[i - values[0]] + 1, coinsUsed[i - values[1]] + 1, coinsUsed[i - values[2]] + 1)
三、求解解决方案,在最少钱币数的条件下,具体使用了哪些钱币,并求出使用了几次。存在多种可能的情况下,输出其中一种可能
coinTimes[i][j]在k < j已经计算出来的情况下,通过步骤二已经确定了这一次使用了哪一张钱币,所以
coinTimes[i][kind] = coinTimes[i - valus[kind]][kind] + 1;
当j != kind的时候
coinTimes[i][j] = coinTimes[i - valus[kind]][j] ;
【题目完整代码】
import java.util.Arrays; public class CoinsChange { /* 程序说明:coinsUsed[i]用来保存总共找i元钱,需要最少的钱币张数 */ /* coinTimes[i][j]用来保存总共找i元钱,需要最少钱币张数时,第j中钱币的使用次数 */ /* solutions[i]用来保存总共找i元钱,所有的可能解决方案的数目 */ public static void makeChange (int[] values, int valueKinds, int money, int[] coinsUsed) { coinsUsed[0] = 0; int[][] coinTimes = new int[money + 1][valueKinds]; int[] solutions = new int[money + 1]; solutions[0] = 1; /* 求解一共有多少种解法 */ for (int kind = 0; kind < valueKinds; kind++) { for (int cents = values[kind]; cents <= money; cents++) { solutions[cents] += solutions[cents - values[kind]]; } } for (int cents = 1; cents <= money; cents++) { int miniCoins = cents; int temp = 0; coinsUsed[cents] = cents; /* 对每一种钱币都进行遍历 */ for (int kind = 0; kind < valueKinds; kind++) { /* 如果当前的面值小于当前要找钱的总钱数 */ if (values[kind] <= cents) { if ((coinsUsed[cents - values[kind]] + 1) <= miniCoins) { coinsUsed[cents] = coinsUsed[cents - values[kind]] + 1; miniCoins = coinsUsed[cents - values[kind]] + 1; /* 保存最终采用的钱币的下标*/ temp = kind; } } } /* 将前面的结果继承下来,并对新采用的钱币数目加1 */ coinTimes[cents] = Arrays.copyOf(coinTimes[cents - values[temp]], valueKinds); coinTimes[cents][temp] = coinTimes[cents - values[temp]][temp] + 1; } System.out.println("总共有" + solutions[money] + "解法,最少需要" + coinsUsed[money] + "张钱币"); for (int kind = 0; kind < valueKinds; kind++) { System.out.println(values[kind] + "元" + coinTimes[money][kind] + "张 "); } } public static void main(String []args) { int[] coinValue = http://www.mamicode.com/new int[] { 3, 2, 1 }; >
【题目变形】上面的情况全部建立在每一种钱币使用次数可以使用无限次,现在的变形是新增一个数组coinsMaxTimes[valuesKind]用来保存每一种钱币限定的最多的使用次数。求解最少使用几张钱币,分别使用了哪些钱币,使用了几次。在上面的基础上,直接给出代码。注意存在找不出来的情形。
import java.util.Arrays; public class CoinsChange { /* 程序说明:coinsUsed[i]用来保存总共找i元钱,需要最少的钱币张数 */ /* coinTimes[i][j]用来保存总共找i元钱,需要最少钱币张数时,第j中钱币的使用次数 */ /* solutions[i]用来保存总共找i元钱,所有的可能解决方案的数目 */ public static void makeChange (int[] values, int valueKinds, int money, int[] coinsUsed, int[] coinMaxTimes) { coinsUsed[0] = 0; int[][] coinTimes = new int[money + 1][valueKinds]; int[] solutions = new int[money + 1]; solutions[0] = 1; int[] flag = new int[money + 1]; flag[0] = 1; for (int cents = 1; cents <= money; cents++) { int miniCoins = cents; int temp = 0; coinsUsed[cents] = cents; /* 对每一种钱币都进行遍历 */ for (int kind = 0; kind < valueKinds; kind++) { /* 如果当前的面值小于当前要找钱的总钱数 */ if (values[kind] <= cents) { if ((coinsUsed[cents - values[kind]] + 1) <= miniCoins) { /* 如果使用该钱币的次数不会超过条件限制的话,刷新,否则不刷新 */ if (((coinTimes[cents - values[kind]][kind] + 1) <= coinMaxTimes[kind]) && ( 1 == flag[cents - values[kind]])) { coinsUsed[cents] = coinsUsed[cents - values[kind]] + 1; miniCoins = coinsUsed[cents - values[kind]] + 1; /* 保存最终采用的钱币的下标*/ temp = kind; flag[cents] = 1; } } } } /* 将前面的结果继承下来,并对新采用的钱币数目加1 */ if (1 == flag[cents]) { coinTimes[cents] = Arrays.copyOf(coinTimes[cents - values[temp]], valueKinds); coinTimes[cents][temp] = coinTimes[cents - values[temp]][temp] + 1; } } if (1 == flag[money]) { System.out.println("最少需要" + coinsUsed[money] + "张钱币"); for (int kind = 0; kind < valueKinds; kind++) { System.out.println(values[kind] + "元" + coinTimes[money][kind] + "张 "); } } else { System.out.println("找不出来"); } } public static void main(String []args) { int[] coinValue = http://www.mamicode.com/new int[] { 5, 3, 1 }; >
硬币找钱问题,求所有可能解决方案数目,最少的钱币数目,每种钱币用多少张