開始動態編程 - 貪婪硬幣更換幫助

Question

我目前正在通過一本關於算法設計的書，並且遇到了一個問題，您必須通過動態編程實現貪婪算法來解決硬幣更換問題。

我試圖實現這一點，我只是無法弄清楚或理解我的書中給出的算法。該算法如下（我的（缺乏）的瞭解，評論）：

Change(p) { 
    C[0] = 0 
    for(i=1 to p) //cycling from 1 to the value of change we want, p 
     min = infinity 
     for(j=1 to k(//cyle from 1 to...? 
      if dj <=i then 
      if(1+C[i-dj] < min) then 
       min = 1+C[i-dj] 
      endif 
      endif 
     endfor 
    C[i] = min 
    endfor 
    return C[p] 
} 

而且我在解釋的嘗試是怎麼回事：

/** 
    * 
    * @param d 
    *   currency divisions 
    * @param p 
    *   target 
    * @return number of coins 
    */ 
    public static int change(int[] d, int p) { 
     int[] tempArray = new int[Integer.MAX_VALUE]; // tempArray to store set 
                 // of coins forming 
                 // answer 
     for (int i = 1; i <= p; i++) { // cycling up to the wanted value 
      int min = Integer.MAX_VALUE; //assigning current minimum number of coints 
      for (int value : d) {//cycling through possible values 
       if (value < i) { 
        if (1 + tempArray[i - value] < min) { //if current value is less than min 
         min = 1 + tempArray[1 - value];//assign it 
        } 
       } 
      } 
      tempArray[i] = min; //assign min value to array of coins 
     } 
     System.out.println("help"); // :(
     return tempArray[p]; 
    } 

可有人請向我解釋什麼，我缺，如何解決這個問題，以及這個算法應該如何工作？動態編程似乎是一個很有用的工具，但我無法理解它。我一直在遞歸地思考。

Answer 1

看到這個wikipedia link

的摘錄：

貪心選擇性質，我們可以做出各種選擇，而在 目前看來最好的，然後解決以後出現的子問題。由貪婪算法所做出的選擇 可能取決於迄今爲止做出的選擇，但不取決於將來的選擇或子問題的所有解決方案。它迭代地做出一個接一個的貪婪選擇，將每個給定的問題減少到一個較小的問題。換句話說，一個貪婪的算法決不會重新考慮它的選擇。這是與動態編程 的主要區別，這是詳盡的，並保證可以找到 解決方案。在每個階段之後，動態規劃根據前一階段做出的所有決策作出決策，並且可能會重新考慮前一階段的解決方案的算法路徑 。

你通過int p代碼迭代得到的最佳選擇，並把它放入數組tempArray然後使用這個值來檢查的最佳選擇在下一次迭代。

Answer 2

動態規劃的本質是將問題分解爲子問題，然後開始構建解決方案。這個想法是，如果你解決「n」個子問題，你可以將它們組合起來，組合就是整個問題的解決方案。遞歸是動態編程的一個例子，但它有潛在的堆棧溢出問題。另一種技術被稱爲memoization，它緩存結果以加快查找速度，而不是重新計算已計算的問題。這節省了大量處理並加快了程序的速度。至於貪婪的硬幣變化問題，其實質是尋找最大的面額並使用它，直到它不能再被使用（即，通過最大面額反覆劃分總金額並跟蹤其餘部分），然後移動到然後重複相同的過程，直到剩下可用最小面額表示的最低金額。您可以一直將最小值存儲在數組中，並在發現新最小值（即記憶）時繼續更新它。我希望人們能糾正我，如果我錯了某處。

編輯：但請注意，並非所有問題都可以通過動態編程來解決，而動態編程與任何編程語言都無關，相反它只是用於解決優化問題的技術名稱。

Answer 3

這似乎是硬件問題，所以我會給出幾點建議。DP解決問題的第一件事就是「思考Top Dwon並解決自下而上問題」。

「想想自上而下」 - 這是你制定你的遞推關係

EG的部分：T（N）= 0如果n < 1或T（N-1），否則，

遞歸關係依賴於先前計算的子問題。

「自下而上」 - 這是您的代碼將根據上面找到的遞歸關係自下而上解決問題的部分。

通常編碼是簡單的，更難的部分是提出一個很好的遞歸關係（雖然不會有遞歸）。

Answer 4

晚會有點晚，但你的功能已經有效。

public static int change(int[] d, int p) { 
    // tempArray to store set of coins forming answer 
    int[] tempArray = new int[Integer.MAX_VALUE]; 

    tempArray[0] = 0; // INITIAL STEP MISSING 

    for (int i = 1; i <= p; ++i) { // cycling up to the wanted value 
     // assigning current minimum number of coins 
     int min = Integer.MAX_VALUE; 

     // cycling through possible values 
     for (int value : d) { 

      if (value <= i) { // FIX missing = in <= 

       // if current value is less than min 
       if (1 + tempArray[i - value] < min) { 

        // FIX, it's [i-value] not [1-value] 
        min = 1 + tempArray[i - value]; 
       } 
      } 
     } 
     tempArray[i] = min; // assign min value to array of coins 
    } 
    return tempArray[p]; 
} 

並使用它。

public static void main(String[] args) { 
    int[] coins = new int[] { 25, 12, 10, 5, 1 }; 

    int coinCount = change(coins, 15); 
    System.out.println("min change: " + coinCount); 
}