貪心算法和硬幣算法

Question

首先，是的，它是我的硬件，我覺得很難，所以我會很感激一些指導。

我需要證明1,x,x2...xn當x>=1硬幣問題的貪婪算法總是工作的面額。

• 當我們總是選擇數量較小的最大硬幣時，我們將始終獲得最小硬幣數量所需的金額。

謝謝。

Answer 1

因爲這是你的功課，我不會提供一個完整的答案而是要設法引導你：

首先，因爲它通常發生於那些類型的問題，試圖證明自己的說法是真實的前幾個自然數。試着總結一下你用什麼來爲他們提供證明。這通常會給你一些正確方法的指導。

我會用induction這一個。

另一種選擇，可以幫助你 - 代表數字系統的所有號碼與基地x。這應該更清楚地說明爲什麼聲明是真實的。

希望這可以幫助你。