Explication détaillée du problème de changement de la programmation dynamique

Problème de changement : le montant de la monnaie requis est W, les valeurs faciales des pièces sont (d1, d2, d3,..., dm), combien de pièces sont nécessaires au moins.

Question : Le montant de la monnaie requis est de 8, les valeurs nominales des pièces sont (1, 3, 2, 5), combien de pièces sont nécessaires au moins.

Soit F(j) représente le nombre minimum de monnaie lorsque le montant total est j, F(0) = 0, W représente le montant de la monnaie, et il y a un tas de monnaie {d1, d2, d3 ,..., dm} . Également basé sur l'expérience antérieure, pour atteindre j, il doit s'agir du nombre de pièces d'une valeur nominale de j – di(1 <= i <= m) plus 1 pièce d'une valeur nominale de di. Bien sûr, j. >= di, c'est-à-dire F (j) = F(j - di) + 1, j >= di. Python3

balise

 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 }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!