解決供應商機器變更問題的Java算法

作爲一名畢業生，我參加了一個java開發角色的面試，在技術考試中表現出色，直到我提出反對這個問題。解決供應商機器變更問題的Java算法

如果我設置了一臺自動售貨機（爲簡單起見）返回£2更改。我將如何產生一個實例，列出所有可能的£2組合。

對於如£1 +£1，£1 + 50P + 50P，50P + 50P + 50P + 50P等..

我怎麼會被列出的2.00£變化可能所有的不同組合售貨機。

我開始寫點東西，這是迄今爲止發明的。

它幾乎工作，除了有人能幫我找出爲什麼它沒有完全擴大。第二雙眼睛會很感激。還有任何可以優化的方法。

謝謝你們。

private static void printCoins(int[] tempArray) { 

    for (int i = 0; i < tempArray.length - 1; i++){ 

// to stop my array from printing out any non-denominator coins e.g 
    if (tempArray[i] > 0){ 
System.out.print(tempArray[i] + ": "); 
    } 
    System.out.println("\n"); 
    } 
} 


public static void vendingMachine() { 
    int[] denominations = {200,100, 50, 20, 10, 5, 2, 1}; 
    int[] tempArray = new int[50]; //combination of coins made 
    int total = 200; 
    int coinCombiIndex = 0, denomCoinIndex = 0; 

    // whilst all denominations havent been visited 
while (denomCoinIndex < denominations.length) 

    // if i have the correct change 
    if (total - denominations[denomCoinIndex] == 0){ 
     tempArray[coinCombiIndex] = denominations[denomCoinIndex]; 

     denomCoinIndex++; //increment so that next iteration starts with lower denom 
     printCoins(tempArray); // return coins 
    } 

// checks to see whether new total minus coin (denominator) is still >= 0 
     else if (total - denominations[denomCoinIndex] >= 0) { 

      // if so SUBTRACT from total and ADD coin to coin-combination-array 
      total = total - denominations[denomCoinIndex]; 
      tempArray[coinCombiIndex] = denominations[denomCoinIndex]; 
      coinCombiIndex++; 

      } 
     else { 
     denomCoinIndex++; 

    } 

    // printCoins(tempArray); 

}

我的輸出

200: 

100: 100: 

100: 50: 50: 

100: 50: 20: 20: 10: 

100: 50: 20: 20: 5: 5: 

100: 50: 20: 20: 5: 2: 2: 1:

來源

2011-08-15 L-Samuels

重複：//stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value – toto2

上面的鏈接是如此受歡迎，它已被製作成社區維基。我想這是一個常見的面試問題。 – toto2

這個問題非常受歡迎，如果您對動態編程進行了一些研究，您會發現詳細討論它。 –

要回答你的第二個問題：

嘗試只用{} 20,10，你會看到你的程序真的是不正確的。

您試圖將我的recurence轉換成循環，我想這是最好的解決方案。但是在一個循環中很難做到這一點（你錯過了很多可能性）。

你可以嘗試reinialise不同的約束while循環，例如每一步增加一個新的，而在你的循環這樣一個

while (i<denominations.length){ 
      total=200; 
      denomCoinIndex=i; 
      tempArray = new int[1000]; 
      i++;

但它仍然不夠環......所以你需要再次添加一些循環，直到你處理所有的情況。

我不認爲你的方法與一個while循環是好的在這裏。

最簡單的方法是使用了這樣的循環來處理所有可能的解決方案（從類似的問題，你的問題）：

int total = 200; 

       System.out. printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total); 

       int combos = 0; 

       for (int q = 0; q <= total/25; q++) 
       { 
        int total_less_q = total - q * 25; 
        for (int d = 0; d <= total_less_q/10; d++) 
        { 
         int total_less_q_d = total_less_q - d * 10; 
         for (int n = 0; n <= total_less_q_d/5; n++) 
         { 
          int p = total_less_q_d - n * 5; 
          System.out.printf("%d\t%d\t%d\t%d\n", q, d, n, p); 
          combos++; 
         } 
        } 
       } 

       System.out.printf("%d combinations\n", combos);

希望它可以幫助HTTP的

來源

2011-08-17 13:11:28

謝謝你，瑞奇，這真的很有幫助。有時嵌套的for-loops會讓我感到遺憾。 –

可能開始在看動態規劃。然而，你可以輕而易舉地解決這個問題。你會怎麼做手動??。記下步驟。將其轉換爲算法。可能學習排列組合&組合將有助於更好地理解你所說的問題。

希望它有幫助。

來源

2011-08-15 15:42:53 panzerschreck

謝謝。你的建議非常值得。 –

重構問題如下：給定一個標準的（現代）汽車裏程表，註冊6個數字，沒有分數，找到所有可能的數值，其中數字的總和是某個值，如15。如果你能解決這個問題，你可以解決給定的問題。

來源

2011-08-15 15:45:00

讓我們說，你可以硬幣X1 ... XN：

，如果你要求打印$ 2所有possiblities那麼你可以打印遞歸一切準備：

2-x1 
2-x2 
.. 
2-xn

Yoou最終會得到所有的解決方案

可以初始化與量璽這個遞歸過程= 0，則打印

來源

2011-08-15 15:46:05

你可以看看我的代碼，並告訴我爲什麼硬幣組合停止在哪裏。我編輯了原來的問題，包括迄今爲止編碼的內容。謝謝 –

@ Lawrence88，好吧我今天會嘗試看看它 –

@ Lawrence88，這是因爲當你找到一個結果時，你試着用第一個較低的工作，而不是所有可能的較低元素。這就是爲什麼你總是在你的解決方案200然後100然後50等你從來沒有100然後2然後。 –

第7頁上的算法F就是您正在尋找的內容。 :)

http://www-cs-staff.stanford.edu/~uno/fasc3a.ps.gz

來源

2011-08-15 16:01:11

-1

public class VendeningMachine 
{ 
    public static final int[] coins = {1, 5, 10, 25}; 
    public static final int[] coinMax = {200, 40, 20, 8}; 
    public static final int[] coinsString = { "Penny", "Nickle", "Dime", "Quarter"}; 

    public static void main(String[] args) 
    { 

    } 


    public static void vendingMachine() 
    { 
     for (int a = 0; a <= coinMax[0]; a++) { 
      for (int b = 0; b <= coinMax[1]; b++) { 
       for (int c = 0; c < coinMax[2]; c++) { 
        for (int d = 0; d < coinMax[3]; d++) { 
         checkCoins(a, b, c, d); 
        } 
       } 
      } 
     } 
    } 

    public static void checkCoins(int penny, int nickle, int dime, int quarter) 
    { 
     int total = coins[0] * penny + coins[1] * nickle + coins[2] * dime + coins[3] * quarter; 

     if (total == 200) 
      printCoins(penny, nickle, dime, quarter); 

    } 

    public static void printCoins(int penny, int nickle, int dime, int quarter) 
    { 
     System.out.println("Penney : " + penny + " Nickle: " + nickle + " Dime: " + dime + " Quarter: " + quarter); 
    } 

}enter code here

來源

2014-04-04 21:56:39 user3499861

請添加一些不屬於代碼的部分來詳細解答答案... – user2284570

解決供應商機器變更問題的Java算法

回答

相關問題