我一直在試圖弄清楚是否有辦法獲得用于進行更改的最佳最小硬幣集。
貪心演算法有一個問題，比如我們有一組硬幣 {1, 5, 6, 9} 并且我們想要得到值 11。然而貪心演算法會給我們 {9,1,1}最優解是 {5, 6}
通過閱讀本網站，我發現這種方法可以為我們提供所需的最少硬幣總數。有沒有辦法從中獲得一組硬幣？
uj5u.com熱心網友回復：
我假設你已經知道了動態規劃方法來發現只有最小數所需的硬幣。假設您想找到最小數量的硬幣來創造總價值K。然后，您的代碼可能是
vector <int> min_coins(K 1);
min_coins[0] = 0; // base case
for(int k = 1; k <= K; k) {
min_coins[k] = INF;
for(int c : coins) { // coins[] contains all values of coins
if(k - c >= 0) {
min_coins[k] = min(min_coins[k], min_coins[k - c] 1);
}
}
}
回答您的問題：為了找到最小尺寸的實際硬幣集，我們可以簡單地保留另一個陣列last_coin[]，其中last_coin[k]等于最后添加到最佳硬幣集的硬幣總和為k。為了說明這一點：
vector <int> min_coins(K 1), last_coin(K 1);
min_coins[0] = 0; // base case
for(int k = 1; k <= K; k) {
min_coins[k] = INF;
for(int c : coins) {
if(k - c >= 0) {
if(min_coins[k - c] 1 < min_coins[k]) {
min_coins[k] = min_coins[k - c] 1;
last_coin[k] = c; // !!!
}
}
}
}
這如何讓你找到這組硬幣？假設我們想找到總和為 的最佳硬幣集K。然后，我們知道last_coin[K]持有集合中的一個硬幣，因此我們可以添加last_coin[K]到集合中。在那之后，我們減去last_coin[K]從K和重復，直到K = 0。顯然，這將構建一個（不一定是）最小大小的硬幣集，其總和為 K。
可能的實作：
int value_left = K;
while(value_left > 0) {
last_coin[value_left] is added to the set
value_left -= last_coin[value_left]
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/357745.html