Change problem: The amount of change required is W, the face values of coins are (d1, d2, d3,..., dm), how many coins are needed at least.
Question: The amount of change required is 8. The face values of coins are (1, 3, 2, 5). How many coins are needed at least.
Let F(j) represent the minimum number of change when the total amount is j, F(0) = 0, W represents the change amount, and there is a pile of change {d1, d2, d3,..., dm} . Also based on previous experience, to achieve j, it must be the number of coins with a face value of j – di(1 <= i <= m) plus 1 coin with a face value of di. Of course, j >= di, that is, 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,……,sum21 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 = j10 for i in range(len(money)):11 if j - money[i] >= 0:12 temp = count[j - money[i]] + 113 if temp < minCoins:14 minCoins = temp15 16 count[j] = minCoins17 18 return count[num]19 20 money = [1, 3, 2, 5]21 num = 822 count = charge_making(money, num)23 print(count)
tag
The above is the detailed content of Detailed explanation of the change problem of dynamic programming. For more information, please follow other related articles on the PHP Chinese website!