Detailed explanation of the change problem of dynamic programming-javaTutorial-php.cn

Detailed explanation of the change problem of dynamic programming

零下一度

Release： 2017-07-20 13:35:00

Original

2821 people have browsed it

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 }

Copy after login

##　Python3

 1 #coding=utf-8 2 def charge_making(money, num): 3     &#39;&#39;&#39; 4     找零问题 5     &#39;&#39;&#39; 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)

Copy after login

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!