java贪心算法找零

Ⅰ 编写程序，采用贪婪法编程实现人民币的找零

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
故：
#include <stdio.h>
int main()
{
int a[6]={100,50,20,10,5,1};//定义金数数目，忽视1块钱以下的。。
int money,tmpMoney=0;
scanf("%d",&money);//输入想要换算成零钱的值。
for(int i=0;i<6;i++){//由于上面数组有六个值。循环六次
while(money>=a[i]){//当钱额小于面值时退出循环
money-=a[i];//当前金额减去面值
tmpMoney++;//保存当前面值的张数
}
printf("%d元的张数为：%d\n",a[i],tmpMoney);
tmpMoney=0;//把这下一次的数量清零
}
}
想要找零设置角和分的可以，只要把类型改为float类。或把值*10倍

Ⅱ C语言，贪心算法，货币找零问题

贪心算法找零就是现实中从最大面额开始找的思路。不代表是最优解，只是算法之一。

由于面额输入顺序不定，我先对输入的面额进行降序排序。

下面代码：

#include <stdio.h>

#include <malloc.h>

int main()

{

int i,j,m,n,*ns=NULL,*cn=NULL,sum=0;

printf("请输入总金额m及零钱种类n："),scanf("%d",&m),scanf("%d",&n);

printf("请分别输入%d种零钱的面额： ",n);

if(!(ns=(int *)malloc(sizeof(int)*n))) return 1;

if(!(cn=(int *)malloc(sizeof(int)*n))) return 1;

for(i=0;i<n;i++) scanf("%d",&ns[i]);

//------------考虑输入面额顺序不定，先对面额进行降序排列（如按照降序输入，该段可删除）

for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i];

//-------------------------------------------------------------------

for(i=0;i<n;i++)//贪心算法，从最大面额开始

if(m>=ns[i])

cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d张 ",ns[i],cn[i]);

printf(" 最少使用零钱%d张 ",sum);

return 0;

}