確定爲給定數量進行更改的組合

我的任務是使用蠻力編寫算法來確定不同方式的數量，即給定數量的相關變化組合。這些更改將使用以下硬幣產生：一分錢（1美分），鎳（5美分），角錢（10美分）和季度（25美分）。確定爲給定數量進行更改的組合

例如

輸入：16（它意味着16美分的變化）

輸出：可以在6周不同的方式被製造，以及它們是：

16便士。
11便士，1個鎳
6便士，1枚硬幣
6個便士，2個鎳
1便士，3個鎳
1便士，1個鎳，1枚硬幣

我算法必須爲指定的變化量產生所有可能的變化組合。

我完全喪失瞭如何開始像這樣的算法。任何投入或洞察力讓我走了會很棒。

來源

2012-03-01 user391686

一個辦法可能是使用了嵌套的每種面額循環和計算總和的最深層次，看它是否在目標量 – PeskyGnat 2012-03-01 14:55:58

+1相匹配要求只是爲了幫助，而不是最後的答案。 – 2012-03-01 15:05:39

[如何找到所有組合的硬幣時給予一定的美元價值]可能的重複（http://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some -dollar-value） – e4c5 2017-04-13 02:53:08

好的。讓我解釋一個蠻力算法的一個想法。我將在這裏使用遞歸。

讓我們您需要更改c美分。然後考慮c作爲

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER

或簡單地說，

c = (p * 1) + (n * 5) + (d * 10) + (q * 25)

現在你需要通過所有可能的值p，n，d和q這等於c值。使用遞歸，每個p in [0, maximumPennies]經過每個n in [0, maximumNickels]。每個n經過每個d in [0, maximumDimes]。對於每個d經過每個q in [0, maximumQuarters]。

p in [0, maximumPennies] AND c >= p 
    | 
    +- n in [0, maximumNickels] AND c >= p + 5n 
     | 
     +- d in [0, maximumDimes] AND c >= p + 5n + 10d 
      | 
      +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q

對於這些步驟中的任何平等，你有一個解決方案。

來源

2012-03-01 15:16:55 Alexander

試着在這個上使用遞歸。您的功能應該採用兩個參數 - 您允許使用的最大值和剩餘金額（您需要首先避免重複）。以這種方式進行功能：如果它在一個微不足道的情況下（例如1,5,10，你可以分別拿一分錢，鎳，角錢）打印這個微不足道的解決方案。同樣對於每種情況，嘗試獲取所有允許類型的一個硬幣（例如不超過允許的最大值）並遞歸繼續。

希望這會有所幫助。

來源

2012-03-01 14:54:13

您可以通過將其分解爲子問題解決這些問題開始思考此問題，然後更改問題並調整解決方案。

在您的情況下，您可以首先嚐試僅使用便士來解決問題（當然只有一個明顯的解決方案），然後查看鎳幣和便士，然後查看所有組合等等。爲了改善這一點，您可以重用算法中早期階段的解決方案。

來源

2012-03-01 14:54:28 Nick

那麼，如果你想要蠻力解決方案，你可以從一個非常天真的recursive approach開始。但爲了高效率，您需要一個dynamic programming approach。

對於遞歸方法：

1. find out the number of ways you can make using penny only. 
2. do the same using penny and nickel only. (this includes step 1 also) 
3. the same using penny, nickel and dime only (including step 2). 
4. using all the coins (with all previous steps).

第一步很簡單，只有一個做到這一點的方式。

對於步驟2中，遞歸應該是這樣的：

number of ways to make n cent using penny and nickel = 
    number of ways to make (n - [1 nickel]) using penny and nickel 
    + number of ways to make n cent using penny only

步驟3：

number of ways to make n cent using penny, nickel and dime = 
    number of ways to make (n - [1 dime]) using penny, nickel and dime 
    + number of ways to make n cent using penny and nickel only

步驟4是相似的。

還有一件事要記住：你可以在一個的方式（即使用零硬幣）使0美分，這是基本情況。

來源

2012-03-01 15:00:45 0605002

+1好聽的解釋！ – hemant 2014-06-26 11:28:27

-1

public class PrintAllCoinCombinations { 


    static int findChange(int arr[], int index , int value, String str){ 

     if(value == 0){ 
      System.out.println(str); 
      return 1; 
     } 
     if(index<0){ 
      return 0; 
     } 
     if(value<0){ 
      return 0; 
     } 

     int excl = findChange(arr,index-1,value,str); 

     str += " "+ arr[index]; 

     int incl = findChange(arr,index,value-arr[index],str); 

     return incl + excl; 

    } 

    public static void main(String [] arg){ 
     int arr[] = {1,5,10,25}; 
     String s = ""; 
     int result = findChange(arr,3,16,s); 
     System.out.println(result); 
    } 
}

來源

2016-06-04 16:50:11

確定爲給定數量進行更改的組合

回答

相關問題