问题描述:
有一个特别的国度，只发行4种面值的硬币，分别是1元硬币，5元硬币，11元硬币，50元硬币。小明去售货机前买饮料，饮料售价35元一瓶，小明投入了50元硬币。现在售货机要找15元钱给他。假设每种硬币的数量充足，现在要求使用最少数量的硬币，给小明找钱，求出这个最少数量是多少。
问题分析:
售货机要给小明找回15元零钱，而现在只有4种面值的硬币可以使用，现在的核心问题是如何使用这4种面值的硬币来凑齐15块钱，且使用的硬币数目最少。
一、要凑齐15元。
二、使用的硬币数目最少。
贪心算法:
每一次尽可能拿出最大的面值钞票找剩下的钱，钱数减去当前钞票的面值，如此循环直到剩下的钱数为0。此算法有例外的情况，假设如今只有3种面值的钞票，分别是1，7，10，要求找出14元钱。贪心算法得到的答案是{10,1,1,1,1}，需要5张钞票，而实际情况下最佳找钱方案是{7,7}，只需要两张钞票。贪心算法保证了每一步取得的是局部最优解，不能保证最终结果是最优解。
动态规划算法:
解决方案：每次只在已知的条件下增加一个一种硬币，使其数额达到找钱数，在这几种方案中选择一个使用硬币数量最小的一种方案。
设f(i) = n :
i为找钱数，取值范围：(0<=i<=15)。
n为凑出i元所需要的硬币数量为n个。
f是使硬币数量n最小的最佳函数。
现在从0元钱开始找:
找0元钱:因为0元根本不需要硬币，所以结果是 f(0) = 0，作为初始化已知条件。
找1元钱:因为只有1元的硬币可以使用，所以可以先用1个1元硬币，然后再凑够0元即可，由于f(0)是我们已经算出来的，并且使用其他硬币均无法达成约束条件，所以
f(1) = 1 + f(0) = 1 + 0 = 1
注意等式f(1) = 1 + f(0)右边的1代表1个1元的硬币，硬币数量。
找2元钱:因为只有1元的硬币可以使用，所以先用1个1元硬币凑出1元钱，然后再凑够1元即可，由于f(1)是我们已经算出来的，并且使用其他硬币均无法达成约束条件，所以
f(2) = 1 + f(1) = 1 + 1 = 2
注意这里f(2) = f(1) + 1，这里加上的1代表1个1元硬币。
找3元钱:重复以上步骤 f(3) = 1 + f(2) = 3。
找4元钱:重复以上步骤 f(4) = 1 + f(3) = 4。
找5元钱:这里就有不一样的选择了，因为有5元硬币可以使用。
方案一：先用1个1元硬币，然后再凑够4元钱，即 1 + f(4) = 5，注意这里的1代表1个1元的硬币；
方案二：先用1个5元硬币，然后再凑够0元钱，即 1 + f(0) = 1，注意这里的1代表1个5元的硬币。
综合两种方案，有 f(5) = min{ 1 + f(4)，1 + f(0) } = 1。
找6元钱:
方案一：先用1个1元硬币，然后再凑够5元钱，1 + f(5) = 2;
方案二：先用1个5元硬币，然后再凑够1元钱，1 + f(1) = 2;
综合两种方案，有 f(6) = min{ 1 + f(5)，1 + f(1) } = 2。
……省略
找15元钱:
方案一：先用1个1元硬币，然后再凑够14元钱，1 + f(14) = 5;
方案二：先用1个5元硬币，然后再凑够10元钱，1 + f(10) = 2;
方案三：先用1个11元硬币，然后再凑够4元钱，1 + f(4) = 5;
综合两种方案，有 f(6) = min{ 1 + f(14)，1 + f(10)， 1 + f(4)} = 2。
跟据上面的分析，要凑够i元，就要考虑如下各种方案的最小值:
f(i) = min{ 1 + f( i – value[j] ) }，i > 1，0 <= j <= num;
value[]存储了各种面值，value[j]表示第j(0<=j<num)种面值，与其中1表示的面值相同。
num表示有多少种面值。
f(0) = 0为已知条件，因此 i > 1。
#include <stdio.h>
const int num = 3; //钱币的面值数
int value[num] = {1,7,11}; //钱币的面值
void change(int n) { //找钱方法
int money[n+1] = {0}, min, note, sum;
int record[n+1] = {0}, num_value[num] = {0}; //record[i]记录i块钱最后用哪张面值的钞票找出，num_value根据record计算出找钱方案
for (int i = 1; i <= n; i++) {
min = n;
for (int j = 0; j < num; j++) {
if (i >= value[j] && min > money[i-value[j]]) {
min = money[i-value[j]]; //在前面几个找钱方案中找出最小的值
note = j; //记录用了哪张钞票
}
}
money[i] = min+1;
record[i] = value[note];
}
printf("最少钱币张数: %d\n", money[n]);
printf("找钱方案:\n");
printf("面值 张数\n");
sum = n;
while (sum > 0) {//有n元钱时，最后用的钞票面值为record[n]
for (int i = 0; i < num; i++)
if (record[sum] == value[i])
num_value[i]++;
sum -= record[sum];
}
for (int i = 0; i < num; i++) {
printf("%d %d\n", value[i], num_value[i]);
}
}
int main() {
int n; //要找的钱数
scanf("%d", &n);
change(n);
return 0;
}
| 
转播
