為找零問題寫一個貪婪演算法偽代碼

① 找零錢問題的貪心演算法

問題描述：
當前有面值分別為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中的面值存放不同面值的硬幣的個數，即找錢方案

② 編寫程序，採用貪婪法編程實現人民幣的找零

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
故：
#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倍

③ 請問數錢的貪婪演算法怎樣確保得到最優解

貪婪演算法：總是作出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解。
（註：貪婪演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。

基本思路：——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

基本要素：
1、 貪婪選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇，即貪婪選擇來達到。（與動態規劃的主要區別）
採用自頂向下，以迭代的方式作出相繼的貪婪選擇，每作一次貪婪選擇就將所求問題簡化為一個規模更小的子問題。
對於一個具體問題，要確定它是否具有貪婪選擇的性質，我們必須證明每一步所作的貪婪選擇最終導致問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪婪選擇開始的，而且作了貪婪選擇後，原問題簡化為一個規模更小的類似子問題。然後，用數學歸納法證明，通過每一步作貪婪選擇，最終可得到問題的一個整體最優解。
2、最優子結構性質:包含子問題的最優解
1、 設有n個活動的安排，其中每個活動都要求使用同一資源，如演講會場，而在同一時間只允許一個活動使用這一資源。每個活動都有使用的起始時間和結束時間。問：如何安排可以使這間會場的使用率最高。
活動 起始時間 結束時間
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14

演算法：一開始選擇活動1，然後依次檢查活動一i是否與當前已選擇的所有活動相容，若相容則活動加入到已選擇的活動集合中，否則不選擇活動i,而繼續檢查下一活動的相容性。即：活動i的開始時間不早於最近加入的活動j的結束時間。
Prodere plan;
Begin
n:=length[e];
a {1};
j:=1;
for i:=2 to n do
if s[i]>=f[j] then
begin a a∪{i};
j:=i;
end
end;

例1 [找零錢] 一個小孩買了價值少於1美元的糖，並將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所採用的貪婪准則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等於要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。

假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1 0美分的硬幣，然後是5美分的，最後加入兩個1美分的硬幣。

貪婪演算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證明採用上述貪婪演算法找零錢時所用的硬幣數目的確最少（見練習1）。

④ python裡面什麼是貪婪

Python裡面的貪婪演算法（又稱貪心演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，/不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是搏孫對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

基本思路

思想

貪心演算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止 。貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

基本思路

思想

貪心演算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止 。貪心演算法彎銀鎮（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

基本思路

思想

貪心演算法的基本思路埋粗是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止 。

⑤ 貪婪法演算法，求找零的最優方案，即從面值最大的開始找零！面值為:100元，50元，10元，5元，1元，0.5,0.1

我幫你把代碼修改了一下

#include<stdio.h>#include<stdlib.h>

#defineMax8

voidexchange(double,int[]);

doublemoneyValues[Max]={100,50,20,10,5,1,0.5,0.1};

intmain(){

inti;

intstore[Max]={0};

doublemoney;

printf("Inputmoneythatyouwillexchange!:");

scanf("%lf",&money);

doublepremoney=money;

exchange(money,store);

printf("%f ",premoney);

for(i=0;i<Max;i++){

if(store[i]>0)

printf("%d:%f ",store[i],moneyValues[i]);

}

return1;

voidexchange(doubleexmoney,intstore[]){

inti;

for(i=0;i<Max;i++){

if(exmoney>moneyValues[i])break;

}

while(exmoney>0&&i<Max){

if(exmoney>moneyValues[i]){

exmoney-=moneyValues[i];

store[i]++;

}elseif(exmoney<0.1&&exmoney>0.05){

store[Max-1]++;

break;

}

elsei++;

}

return;

然後，我覺得有些地方你寫得啰嗦了，幫你簡化了一下

#include<stdio.h>#include<stdlib.h>

#defineMax8

voidexchange(double,int[]);

doublemoneyValues[Max]={100,50,20,10,5,1,0.5,0.1};

intmain(){

inti;

intstore[Max]={0};

doublemoney;

printf("Inputmoneythatyouwillexchange!:");

exchange(money,store);

printf("%f ",money);

for(i=0;i<Max;i++){

if(store[i]>0)

printf("%d:%f ",store[i],moneyValues[i]);

}

return1;

voidexchange(doublemoney,intstore[]){

inti=0;

while(money>0&&i<Max){

if(money>moneyValues[i]){

money-=moneyValues[i];

store[i]++;

}elseif(money<0.1&&money>0.05){

store[Max-1]++;

break;

}

elsei++;

}

return;

⑥ 寫出演算法的偽代碼

偽代碼(Pseudocode)是一種演算法描述語言。使用為代碼的目的是為了使被描述的演算法可以容易地以任何一種編程語言(Pascal, C, Java, etc)實現。因此，偽代碼必須結構清晰，代碼簡單，可讀性好，並且類似自然語言。

下面介紹一種類Pascal語言的偽代碼的語法規則。

偽代碼的語法規則
在偽代碼中，每一條指令佔一行(else if 例外，)，指令後不跟任何符號（Pascal和C中語句要以分號結尾）；
書寫上的「縮進」表示程序中的分支程序結構。這種縮進風格也適用於if-then-else語句。用縮進取代傳統Pascal中的begin和end語句來表示程序的塊結構可以大大提高代碼的清晰性；同一模塊的語句有相同的縮進量，次一級模塊的語句相對與其父級模塊的語句縮進；
例如：

line 1
line 2
sub line 1
sub line 2
sub sub line 1
sub sub line 2
sub line 3
line 3
而在Pascal中這種關系用begin和end的嵌套來表示，

line 1
line 2
begin
sub line 1
sub line 2
begin
sub sub line 1
sub sub line 2
end;
sub line 3
end;
line 3在C中這種關系用{ 和 } 的嵌套來表示，

line 1
line 2
{
sub line 1
sub line 2
{
sub sub line 1
sub sub line 2
}
sub line 3
}
line 3
在偽代碼中，通常用連續的數字或字母來標示同一即模塊中的連續語句，有時也可省略標號。
例如：

1. line 1
2. line 2
a. sub line 1
b. sub line 2
1. sub sub line 1
2. sub sub line 2
c. sub line 3
3. line 3符號△後的內容表示注釋；
在偽代碼中，變數名和保留字不區分大小寫，這一點和Pascal相同，與C或C++不同；
在偽代碼中，變數不需聲明，但變數局部於特定過程，不能不加顯示的說明就使用全局變數；
賦值語句用符號←表示，x←exp表示將exp的值賦給x，其中x是一個變數，exp是一個與x同類型的變數或表達式（該表達式的結果與x同類型）；多重賦值i←j←e是將表達式e的值賦給變數i和j，這種表示與j←e和i←e等價。
例如：

x←y
x←20*(y+1)
x←y←30
以上語句用Pascal分別表示為：

x := y;
x := 20*(y+1);
x := 30; y := 30;
以上語句用C分別表示為：

x = y;
x = 20*(y+1);
x = y = 30;
選擇語句用if-then-else來表示，並且這種if-then-else可以嵌套，與Pascal中的if-then-else沒有什麼區別。
例如:

if (Condition1)
then [ Block 1 ]
else if (Condition2)
then [ Block 2 ]
else [ Block 3 ]
循環語句有三種：while循環、repeat-until循環和for循環，其語法均與Pascal類似，只是用縮進代替begin - end；
例如：

1. x ← 0
2. y ← 0
3. z ← 0
4. while x < N
1. do x ← x + 1
2. y ← x + y
3. for t ← 0 to 10
1. do z ← ( z + x * y ) / 100
2. repeat
1. y ← y + 1
2. z ← z - y
3. until z < 0
4. z ← x * y
5. y ← y / 2
上述語句用Pascal來描述是：

x := 0;
y := 0;
z := 0;
while x < N do
begin
x := x + 1;
y := x + y;
for t := 0 to 10 do
begin
z := ( z + x * y ) / 100;
repeat
y := y + 1;
z := z - y;
until z < 0;
end;
z := x * y;
end;
y := y / 2;
上述語句用C或C++來描述是：

x = y = z = 0;
while( z < N )
{
x ++;
y += x;
for( t = 0; t < 10; t++ )
{
z = ( z + x * y ) / 100;
do {
y ++;
z -= y;
} while( z >= 0 );
}
z = x * y;
}
y /= 2;
數組元素的存取有數組名後跟「[下標]」表示。例如A[j]指示數組A的第j個元素。符號「 …」用來指示數組中值的范圍。
例如：

A[1…j]表示含元素A[1], A[2], … , A[j]的子數組；

復合數據用對象(Object)來表示，對象由屬性(attribute)和域(field)構成。域的存取是由域名後接由方括弧括住的對象名表示。
例如：

數組可被看作是一個對象，其屬性有length，表示其中元素的個數，則length[A]就表示數組A中的元素的個數。在表示數組元素和對象屬性時都要用方括弧，一般來說從上下文可以看出其含義。

用於表示一個數組或對象的變數被看作是指向表示數組或對象的數據的一個指針。對於某個對象x的所有域f，賦值y←x就使f[y]=f[x]，更進一步，若有f[x]←3，則不僅有f[x]=3，同時有f[y]=3，換言之，在賦值y←x後，x和y指向同一個對象。

有時，一個指針不指向任何對象，這時我們賦給他nil。

函數和過程語法與Pascal類似。
函數值利用 「return (函數返回值)」 語句來返回，調用方法與Pascal類似；過程用 「call 過程名」語句來調用；

例如：

1. x ← t + 10
2. y ← sin(x)
3. call CalValue(x,y)
參數用按值傳遞方式傳給一個過程：被調用過程接受參數的一份副本，若他對某個參數賦值，則這種變化對發出調用的過程是不可見的。當傳遞一個對象時，只是拷貝指向該對象的指針，而不拷貝其各個域。

⑦ vb 求編程 找零問題 要求找出錢幣最少（只有1，5,10,20,50元），請設計函數change輸出找零方案

給個思路吧.
你這個題的意思寫的不明確,我想這個函數大概是需要一個價格,和一個給的金額.
設定變數, num50,num20,num10,num5,num1 需要找的零錢的數量.
首先 ,金額-價格=找零,如果找零=0 就不用說了.
然後, 找零/50 ,得出需不需要50的.用找零mod/50 得出還需要找多少. 這里可以做判斷,如果找零>0 並且 找零/50>0 ,並且 找零 mod 50 =0 ,也就是說找一張50的就可以了,那就結束函數
以此類推
找零餘額/20 ,找零餘額 mod 20 .... 判斷是否找夠....

⑧ 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;

}