文档介绍：找零钱问题的贪心算法
问题描述:
当前有面值分别为2角5分,1角,5分,1分的硬币,请给出找n分钱的最佳方案(要求找出的硬币数目最少)
问题分析:
根据常识,我们到店里买东西找钱时,老板总是先给我们最大面值的,要是不够再找面值小一点的,直到找满为止。如果老板都给你找分数的或者几角的,那你肯定不干,另外,他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现:
先举个例子,假如老板要找给我99分钱,他有上面的面值分别为25,10,5,1的硬币数,为了找给我最少的硬币数,那么他是不是该这样找呢,先看看该找多少个25分的, 99/25=3,好像是3个,要是4个的话,我们还得再给老板一个1分的,我不干,那么老板只能给我3个25分的拉,由于还少给我24,所以还得给我2个10分的和4个1分。
具体实现
//找零钱算法
//By falcon
//输入:数组m,依次存放从大到小排列的面值数,n为需要找的钱数,单位全部为分
//输出:数组num,对照数组m中的面值存放不同面值的硬币的个数,就找钱方案
public static int[] zhaoqian(int m[],int n)
{
int k=;
int[] num=new int[k];
for(int i=0;i<k;i++)
{
num<i>=n/m<i>;
n=n%m<i>;
}
return num;
}
public class zhaoqian
{
public static void main(String[] args)
{
int m[]={25,10,5,1};
int n=99;
int[] num=new int[];
num=zhaoqian(m,n);
(n+"的找钱方案:");
for(int i=0;i<;i++)
(num<i>+"枚"+m<i>+"面值");
}
public static int[] zhaoqian(int m[],int n)
{
int k=;
int[] num=new int[k];
for(int i=0;i<k;i++)
{
num<i>=n/m<i>;
n=n%m<i>;
}
return num;
}
}
#include <>
#include <>
#define M 10
using namespace std;
int Coinsbackup[6];
int Coin_Face[6]={5,10,20,50,100,200};
int Number_of_Money(int Coins[6],int Coin_Face[6],double X,int Y,int Z)
{
int back1[6]={5,10,20,50,100,200};
int back2[11]={15,25,30,40,55,60,70,105,110,120,150};
in