硬币找零问题（动态规划）

硬币找零（动态规划）

问题介绍

给定指定的硬币种类，面值为 1, 3, 5（在此具体化些），给定所找零的钱数 sum，给出最少的硬币找零数，每个种类的硬币无限使用。

问题分析

看到这问题，当时我想到用贪心算法来求解，最后求解方案因为巧合对了，后来在网上看到动态规划的题目，才知道贪心算法得不到最优解，比如 给定 面值为 1, 3, 4，给定找零数为 6，用贪心法得出方案 [4,1,1],但显然 [3,3] 方案即可。分析下问题，想一下若存在最少硬币数 num 满足当前给定的找零数 sum，则是不是一定存在最少硬币数 num-1 满足找零数 sum - （1, 3, 5 )？答案是存在，想一想就知道，当然边界除外。这个类似于最短路径的 dijkstra算法。

实现方案

对于上面这个思路的实现方案，我用的是回溯思想，撸一个递归函数，不断递归查找给定硬币数，给定金额的方案。在此设置一个标志位 is_find ，若找到 赋值为 true 。在外面套一层循环使得 硬币数 从 1 不断增加，若找不到则 硬币数 + 1 继续找，若找到 则退出循环（通过判断 is_find ), 找的过程中需要保存数据，在此声明一个数组变量 coin_kind 保存方案，每次递归将下标为 num 的数组元素设置为 当前选择的硬币值，这是回溯的思想，具体看代码。

代码

#include<stdio.h>
#include<stdlib.h>
int coin[3] = {1, 3, 5};			/* 硬币种类	*/ 
int coin_kind_num = 3;				/* 硬币种类数量 */ 
int sum = 7;						/* 找零钱数 */  
int min_coin_num;					/* 硬币最少数 */ 
int coin_kind[1000];				/* 存放最少数的方案 */ 
bool is_find = false;				/* 是否找到硬币 */ 

/*  函数：打印方案
	打印存放找零方案的 数组coin_kind[]  
*/ 
bool output(){
	for (int i = 0; i < 1000; i++)
	{
		if (coin_kind[i] == -1) break;
		printf("   %d ", coin_kind[i]);
		
	}
	printf("\n");
}

/* 	函数：初始化方案数组 
	初始化存放找零方案的数字 ，使元素全部为 0，以便判断输出 
*/
void initCoinKind(){
	for (int i = 0; i < 100; i++) coin_kind[i] = -1;
}

/* 函数：查找基本函数 
   该函数用于给定 指定硬币数 和 指定应找零的钱数，看是否能找开，用的回溯法查找.
   思想是 若存在对于给定应找零的钱数 sum，存在最少硬币数 num，则对于 sum - coin[i] ( i = 0, ..., coin_kind_num - 1)
   仍然存在最少硬币数 num - 1, 类似于 最短路径那个 dijkstra算法 。 
    
   @param   num    指定硬币数
   @param   sum    指定应找零的钱数	 
 */
bool findCoin(int num, int sum){
	
	/* 函数逻辑
		
		若 给定指定硬币数为 0 , 即此时已到期待边界，若此时硬币数
			等于 0 ，说明已经找开，找到方案，赋值 is_find = true ( 作为 连续查找终止条件 )。
			大于 0 ，说明未找开， 此时剩余应找开金额大于0。 
			小于 0 , 说明此时剩余金额小于 0，不满足。 
		若 给定指定金额硬币数 不为 0（及 大于 0），说明此时未搜寻完，执行
			遍历存放硬币种类的数组 coin[]， 将当前遍历对象 存放到 *指定下标* 的 
			找零方案数组 coin_kind[] 中。递归执行 该函数，硬币数 - 1，应找零数 - 遍历对象硬币值 
	
	*/
	
	if (num == 0)					
	{
		if (sum == 0){
			is_find = true;
			printf("找到最少硬币数 %d: ", min_coin_num); 
			output();
			return true;
		} else if (sum > 0){
		
			return false;
		} else{
		
			return false;
		}
	}
	else
	{
		for (int i = 0; i < coin_kind_num; i++)
		{
			coin_kind[num - 1] = coin[i];
			findCoin(num - 1, sum - coin[i]);
		}
	}
} 

/* 	函数：硬币数逐渐 + 1 查找 
	由于查找方案基本函数只能给定指定硬币数 num 和指定找零数 sum，
	所以 应该使得指定硬币数从小到大， 从 1 开始，每次查找完毕判断 is_find 的值，
	若为 false 则 num + 1，继续查找
	否则 退出循环查找完毕。 

 */ 
bool startFind(){
	int num = 1;
	while (!is_find){
		min_coin_num = num;
		findCoin(num, sum);
		num++;
	}
}
int main(){
	initCoinKind();		/* 初始化存放方案的数组 */ 
	startFind();
}

总结

思想是动态规划的思想，动态规划有个动态方程，感觉这个问题动态方程比较简单，写出来可能还不如描述下思想，我感觉重点在于怎么保存找的方案，在此用的回溯法不断的重写固定下标的元素，这一点很重要。另外，该算法使用递归，并且没有保存当前状态，有优化的空间，可以用递归法。