L'idée de base de la programmation dynamique est de décomposer le problème à résoudre dans plusieurs sous-problèmes, de résoudre d'abord les sous-problèmes et de sauver les solutions de ces sous-problèmes. Si vous avez besoin d'utiliser les solutions de ces sous-problèmes à l'avenir lorsque vous résolvez des sous-problèmes plus importants, vous pouvez extraire directement ces solutions calculées pour éviter les opérations répétées. La solution pour enregistrer les sous-problèmes peut être remplie en utilisant la méthode de formulaire, telle que la sauvegarde dans un tableau.
Utilisez un exemple pratique pour refléter l'idée algorithmique de la programmation dynamique - le problème du changement de pièce.
Description de la question:
Supposons qu'il y ait plusieurs pièces et qu'il y a des quantités illimitées. Veuillez découvrir le nombre minimum de pièces qui peuvent constituer un certain nombre de changements. Par exemple, plusieurs types de pièces sont [1, 3, 5], le nombre minimum de pièces avec une valeur nominale de 2 est de 2 (1, 1), le nombre minimum de pièces avec une valeur nominale de 4 est de 2 (1, 3), et le nombre minimum de pièces avec une valeur nominale de 11 est de 3 (5, 5, 1 ou 5, 3, 3).
Analyse des problèmes:
Supposons que les différents ensembles de pièces sont des pièces de monnaie [0, ..., n-1]. Puis trouvez le nombre minimum de pièces avec la valeur nominale K, puis la fonction de comptage et la pièce de monnaie de pièces répondent à cette condition:
Count (k) = min (count (k - pièces [0]), ..., count (k - pièce [n - 1])) + 1;
Et la formule précédente ne tient que si la condition K - Coin [i]> = 0 && k - Coin [i] <k est remplie.
Parce que K - Coin [i] <k, lors du calcul du nombre (k), le nombre (i) (i <- [0, k-1]) doit être satisfait, donc ici implique le problème de retour en arrière.
Nous pouvons donc créer une matrice matricielle [K + 1] [Coin.Length + 1], de sorte que la matrice [0] [J] est toutes initialisées à 0 valeurs, et enregistrer le nombre minimum de pièces avec une valeur faciale de I dans la matrice [i] [Coin.Length].
Et le processus spécifique est le suivant:
* K | COIN 1 3 5 min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2 2, 2, 2, 2 * ...
Enfin, l'implémentation spécifique du code Java est la suivante:
public static int backtrackingCoin (int [] pièces, int k) {// méthode de retour de retour + programmation dynamique if (coins == null || coins.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [coins.length + 1]; for (int i = 1; i <= k; i ++) {for (int j = 0; j <coins.length; j ++) {int prek = i - coins [j]; if (prek> -1) {// uniquement lorsqu'il n'est pas inférieur à 0, Prek peut exister dans la matrice du tableau et le retour de retour en arrière peut être effectué. matrix[i][j] = matrix[preK][coins.length] + 1;//The face value i is backtracking if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//If the current number of coins is the smallest, update the minimum number of coins in the min column matrice [i] [coins.length] = matrice [i] [j]; }}} Retour Matrix [k] [coins.length]; }Le code a été testé et tous les cas de test donnés par la question sont passés!
Résumer
Ce qui précède est l'intégralité du contenu de cet article sur le code d'implémentation du problème de changement de pièce de la programmation dynamique Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!