问题描述:
有一个特别的国度，只发行
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(1
0
)，
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;
}