Home > Java > javaTutorial > body text

Detailed explanation of the change problem of dynamic programming

零下一度
Release: 2017-07-20 13:35:00
Original
2851 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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Recommendations
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template