動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法–動態(tài)規(guī)劃。1957年出版了他的名著《Dynamic Programming》，這是該領(lǐng)域的第一本著作。

動態(tài)規(guī)劃一般可分為線性動規(guī)，區(qū)域動規(guī)，樹形動規(guī)，背包動規(guī)四類。舉例:線性動規(guī):攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等;區(qū)域動規(guī):石子合并， 加分二叉樹，統(tǒng)計單詞個數(shù)，炮兵布陣等;樹形動規(guī):貪吃的九頭龍，二分查找樹，聚會的歡樂，數(shù)字三角形等;背包問題:01背包問題，完全背包問題，多重背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶(同濟ACM第1132題)等;

文章主要介紹了Java動態(tài)規(guī)劃之硬幣找零問題實現(xiàn)代碼，具有一定參考價值，需要的朋友可以了解下。

動態(tài)規(guī)劃的基本思想是將待求解問題分解成若干個子問題，先求解子問題，并將這些子問題的解保存起來，如果以后在求解較大子問題的時候需要用到這些子問題的解，就可以直接取出這些已經(jīng)計算過的解而免去重復運算。保存子問題的解可以使用填表方式，例如保存在數(shù)組中。\

用一個實際例子來體現(xiàn)動態(tài)規(guī)劃的算法思想——硬幣找零問題。

問題描述:

假設(shè)有幾種硬幣，并且數(shù)量無限。請找出能夠組成某個數(shù)目的找零所使用最少的硬幣數(shù)。例如幾種硬幣為[1, 3, 5], 面值2的最少硬幣數(shù)為2(1, 1), 面值4的最少硬幣數(shù)為2(1, 3), 面值11的最少硬幣數(shù)為3(5, 5, 1或者5, 3, 3).

問題分析:

假設(shè)不同的幾組硬幣為數(shù)組coin[0, ..., n-1]. 則求面值k的最少硬幣數(shù)count(k), 那么count函數(shù)和硬幣數(shù)組coin滿足這樣一個條件:

count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
并且在符合條件k - coin[i] >= 0 && k - coin[i] < k的情況下, 前面的公式才成立.
因為k - coin[i] < k的緣故, 那么在求count(k)時, 必須滿足count(i)(i <- [0, k-1])已知, 所以這里又涉及到回溯的問題.

所以我們可以創(chuàng)建一個矩陣matrix[k + 1][coin.length + 1], 使matrix[0][j]全部初始化為0值, 而在matrix[i][coin.length]保存面值為i的最少硬幣數(shù).

具體的過程如下:

* k|coin 1  3  5  min
 * 0    0  0  0  0
 * 1    1  0  0  1
 * 2    2  0  0  2
 * 3    3  1  0  3, 1
 * 4    2  2  0  2, 2
 * 5    3  3  1  3, 3, 1
 * 6    2  2  2  2, 2, 2
 * ...

最后, 具體的Java代碼實現(xiàn)如下:

public static int backTrackingCoin(int[] coins, int k) {//回溯法+動態(tài)規(guī)劃
    if (coins == null || coins.length == 0 || k < 1) {
      return 0;
    }
    int[][] matrix = new int[k + 1][coins.length + 1];
    for (int i = 1; i <= k; i++) {
      for (int j = 0; j < coins.length; j++) {
        int preK = i - coins[j];
        if (preK > -1) {//只有在不小于0時, preK才能存在于數(shù)組matrix中, 才能夠進行回溯.
          matrix[i][j] = matrix[preK][coins.length] + 1;//面值i在進行回溯
          if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//如果當前的硬幣數(shù)目是最少的, 更新min列的最少硬幣數(shù)目
            matrix[i][coins.length] = matrix[i][j];
          }
        }
      }
    }
    return matrix[k][coins.length];
  }

代碼經(jīng)過測試, 題目給出的測試用例全部通

到此這篇關(guān)于Java動態(tài)規(guī)劃之硬幣找零問題實現(xiàn)示例的文章就介紹到這了,更多相關(guān)Java 硬幣找零內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論