C++貪婪演算法程式問題

Question

利用貪婪演算法找幣值
輸入：一數值
輸出：依照台灣現有發行幣值找出最佳解
例如：輸入　９8７７
　　　輸出　4*2000
1*1000
1*500
1*200
1*100
1*50
2*10
1*5
2*1
求這個程式 如何寫

200元的 要除用200除於多少?

200的 我加上
h=i/200;
printf("%d*200\n",h);
i=guess%200

100元那邊會多跑一次

Answer 1

#include
#include
#include

using namespace std;

int main(void)
{
int guess;
int a,b,c,d,e,f,g;
int i;
cout << "請輸入一數值：";
cin >> guess;
a=guess/2000;
printf("%d*2000\n",a);
i=guess%2000;
b=i/1000;
printf("%d*1000\n",b);
i=guess%1000;
c=i/500;
printf("%d*500\n",c);
i=guess%500;
d=i/100;
printf("%d*100\n",d);
i=guess%100;
e=i/50;
printf("%d*50\n",e);
i=guess%50;
f=i/10;
printf("%d*10\n",f);
i=guess%10;
g=i/5;
printf("%d*5\n",g);
i=guess%5;
printf("%d*1\n",i);
return 0;
}

2006-08-24 09:52:31 補充：
需要註解嗎？台幣好像還有二十塊銅板跟200紙鈔沒算進去用總數去除餘計算就行了很簡單

2006-08-24 10:53:41 補充：
甚麼是Greedy?貪婪演算法？書上沒看過說
雖然題目我會做，不過寫法不知對不對

2006-08-24 17:12:33 補充：
中間這段這樣改，我解釋一下好了printf("%d*500\n",c);i=guess%500; //i=輸入值除以500的餘數h=i/200;// h=500的餘數再除200printf("%d*200\n",h);//因為定義是整數，所以不用理會整除後的小數點i=guess%200;d=i/100;printf("%d*100\n",d);

2006-08-24 17:19:46 補充：
我不知道你2006-08-24 10:12:36 補充200的 我加上h=i/200;printf("%d*200n",h);i=guess%200 100元那邊會多跑一次的程式是加在那個位址，很難判斷你錯再那裡你可以試著用我程式開頭2000慢慢自己往下推斷寫一段就試一段程式，這樣會比較容易弄懂

2006-08-24 17:26:31 補充：
1. Greedy choice property (如其敘述) 這個條件我還是看不明白


2. Optimal sub-structure (這個是指問題的結構,這問題如果取一部份來看仍然是最佳解)
這個條件我的程式跟ASD的第二個
程式倒是符合，但ASD的寫法簡短很多....新手可能比較難看懂

Answer 2

網路上的資料(貪婪演算法)，我也看不懂，最好還是看課本比較快，假如課本有虛擬碼就好寫了…

連我自己都差點忘了有「新台幣 2000 元」的幣值…

Answer 3

要符合Greedy Method要符合由區域最佳解推廣到全域最佳解....

1. Greedy choice property (如其敘述)
2. Optimal sub-structure (這個是指問題的結構,這問題如果取一部份來看仍然是最佳解)

2006-08-25 04:24:55 補充：
Greedy choice property
就是一種貪心的策略
比如說...取價錢最大
取價值最小
舉個可分割的0-1背袋問題
在這問題的Greedy choice property 就是取單價(價錢/重量)最高....

Answer 4

為什麼這題可以用 Greedy?
怎麼證明阿? 都不懂耶 O.o

2006-08-24 11:52:28 補充：
對阿, 貪婪演算法, 有兩個特性:

1. Greedy choice property
2. Optimal sub-structure

這提要怎麼看符合這兩個? 教科書都看不太懂證明

2006-08-24 13:11:32 補充：
謝謝了, 看來滿難掌握的!
.