Detaillierte Erläuterung des Änderungsproblems der dynamischen Programmierung

Wechselgeldproblem: Der benötigte Wechselgeldbetrag ist W, die Nennwerte der Münzen sind (d1, d2, d3,..., dm), wie viele Münzen werden mindestens benötigt.

Frage: Der benötigte Wechselgeldbetrag beträgt 8, die Nennwerte der Münzen sind (1, 3, 2, 5), wie viele Münzen werden mindestens benötigt.

Sei F(j) die minimale Anzahl an Wechselgeldern, wenn der Gesamtbetrag j ist, F(0) = 0, W den Wechselgeldbetrag darstellt und es einen Wechselgeldhaufen {d1, d2, d3 gibt ,..., dm} . Basierend auf früheren Erfahrungen muss es, um j zu erreichen, die Anzahl der Münzen mit einem Nennwert von j sein – di(1 <= i <= m) plus 1 Münze mit einem Nennwert von di >= di, das heißt F (j) = F(j - di) + 1, j >= di. Python3

Tag

 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 }

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung des Änderungsproblems der dynamischen Programmierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!