硬幣更改：貪婪的方法

問題是使用美分，美分，鎳和便士來改變美分，並使用最少的硬幣總數。在四種面值爲四分錢，硬幣，五分錢和便士的特殊情況下，我們有c1 = 25，c2 = 10，c3 = 5，c4 = 1。硬幣更改：貪婪的方法

如果我們有只有四分之一，和便士（無鎳）使用，貪心算法會做出改變，使用6枚硬幣 -a季度和五個30美分硬幣，而我們也可以使用三枚硬幣，即，三角錢。

給定一組衡量標準，我們怎麼能說貪婪方法是否創建了最優解？

2015-05-09 bhavya

你問這個怎麼解決？有一個簡單的動態編程解決方案。 –

@AmiTavory我讀的是謹慎的數學，這是羅森的應用，他在他的書中引用了這個例子。即使我認爲問題類似於揹包問題，並且對一個貪婪的解決方案感到驚訝 – bhavya

對不起，但（至少）我不明白你到底在問什麼。也許你可以編輯你的問題一點。 –

你在問什麼是如何決定一個給定的硬幣系統是規範爲變化的問題。如果貪婪算法總是提供最佳解決方案，則系統是規範的。您可以決定一個包含1美分片的硬幣系統是否爲有限數量級的標準。在某些情況下，詳細信息以及更高效的算法可以在http://arxiv.org/pdf/0809.0400.pdf中找到。

2015-05-10 22:56:31

回答