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

創(chuàng)新互聯(lián)專注于企業(yè)成都營銷網(wǎng)站建設(shè)、網(wǎng)站重做改版、米脂網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5網(wǎng)站設(shè)計、商城開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為米脂等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

用一個實際例子來體現(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
  * ...

本文標(biāo)題：Java動態(tài)規(guī)劃之硬幣找零問題實現(xiàn)代碼-創(chuàng)新互聯(lián)
鏈接URL：http://www.aaarwkj.com/article40/ccdeeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、App開發(fā)、網(wǎng)站建設(shè)、定制網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)