動態規劃之找零問題詳解

　　找零問題：需找零金額為W，硬幣面額有(d1, d2, d3，…，dm)，最少需要多少枚硬幣。

　　問題：需找零金額為8，硬幣面額有(1, 3, 2, 5)，最少需要多少枚硬幣。

　　設F(j)表示總金額為j時最少的零錢數，F(0) = 0，W表示找零金額，有零錢一堆{d1, d2, d3，…，dm} 。同樣根據先前的經驗，要達到為j，那麼必然是j – di(1 = di，即F (j) = F(j - di) + 1, j >= di。

　　Java

 1 package com.algorithm.dynamicprogramming; 2  3 import java.util.Arrays; 4  5 /** 6  * 找零问题 7  * Created by yulinfeng on 7/5/17. 8  */ 9 public class Money {10     public static void main(String[] args) {11         int[] money = {1, 3, 2, 5};12         int sum = 8;13         int count = money(money, sum);14         System.out.println(count);15     }16 17     private static int money(int[] money, int sum) {18         int[] count = new int[sum + 1];19         count[0] = 0;20         for (int j = 1; j = 0) {24                     int temp = count[j - money[i]] + 1; //当前所需硬币数25                     if (temp 

　　Python3

 1 #coding=utf-8 2 def charge_making(money, num): 3     ''' 4     找零问题 5     ''' 6     count = [0] * (num + 1) 7     count[0] = 0 8     for j in range(1, num + 1): 9         minCoins = j10         for i in range(len(money)):11             if j - money[i] >= 0:12                 temp = count[j - money[i]] + 113                 if temp 

tag

#

以上是動態規劃之找零問題詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！