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;

}