【标题简短】
现有在一堆脸值对于 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 = new int[] { 3, 2, 1 }; //保存用于保存钱币面值的数组
int money;//要找钱的总数【题目解决方式】
动态递归思想
一、求解一共同拥有多少种解决方式
如果这一堆面值分别为 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 = new int[] { 3, 2, 1 };
int money = 4;
int[] coinsUsed = new int[money + 1];
makeChange(coinValue, coinValue.length, money, coinsUsed);
}
}
【题目变形】
上面的情况所有建立在每一种钱币使用次数能够使用无限次，如今的变形是新增一个数组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 = new int[] { 5, 3, 1 };
int[] coinMaxTimes = new int[] {1, 3, 1};
int money = 19;
int[] coinsUsed = new int[money + 1];
makeChange(coinValue, coinValue.length, money, coinsUsed, coinMaxTimes);
}
}