找零问题:需找零金额为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 <= i <= m)面值的硬币数再加1个di面值的硬币,当然j >= 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 < sum + 1; j++) { //总金额数,1,2,3,……,sum
21 int minCoins = j;
22 for (int i = 0; i < money.length; i++) { //遍历硬币的面值
23 if (j - money[i] >= 0) {
24 int temp = count[j - money[i]] + 1; //当前所需硬币数
25 if (temp < minCoins) {
26 minCoins = temp;
27 }
28 }
29 }
30
31 count[j] = minCoins;
32 }
33 System.out.println(Arrays.toString(count));
34 return count[sum];
35 }
36 }
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 = j
10 for i in range(len(money)):
11 if j - money[i] >= 0:
12 temp = count[j - money[i]] + 1
13 if temp < minCoins:
14 minCoins = temp
15
16 count[j] = minCoins
17
18 return count[num]
19
20 money = [1, 3, 2, 5]
21 num = 8
22 count = charge_making(money, num)
23 print(count)
tag