L'idée de base de l'algorithme gourmand
1. Établir un modèle mathématique pour décrire le problème.
2. Divisez les problèmes résolus en plusieurs sous-problèmes.
3. Résolvez chaque sous-problème et obtenez la solution optimale locale au sous-problème.
4. Synthétisez la solution optimale locale du sous-problème dans une solution à la solution d'origine du problème.
Le processus de mise en œuvre de cet algorithme:
À partir d'une certaine solution initiale au problème;
Tout en puisse passer à un objectif global donné
Trouver un élément de solution de la solution réalisable;
Une solution réalisable au problème est composée de tous les éléments de solution.
Nature sélective gourmande
La nature dite de sélection gourmand signifie que la solution optimale globale du problème que vous recherchez peut être réalisée grâce à une série de choix optimaux locaux. Problème actuel sans le considérer. Il s'agit du premier élément de base de la faisabilité des algorithmes gourmands.
Les algorithmes gourmands font des choix itérativement gourmands, et chaque fois qu'un choix gourmand est fait, le problème que vous recherchez est réduit à un sous-problème plus petit.
Pour un problème spécifique, pour déterminer s'il a une nature de choix gourmand, il est nécessaire de prouver que le choix gourmand fait à chaque étape conduit finalement à la solution optimale globale au problème.
2. Propriétés optimales de substructure <Br /> Lorsque la solution optimale d'un problème contient la solution optimale de son sous-problème, ce problème aurait les propriétés sous-structurales optimales. La nature de la sous-structure optimale du problème est une caractéristique clé qui peut être résolue par des algorithmes gourmands.
Le processus général de la cupidité
La copie de code est la suivante:
Gourmand (c) // c est l'ensemble d'entrée du problème, c'est-à-dire l'ensemble candidat
{
S = {};
tandis que (pas des solutions) // set S ne constitue pas une solution au problème
{
x = select (c);
Si faisable (s, x) // juger si la solution après avoir ajouté X à l'ensemble s est possible
S = s + {x};
C = c- {x};
}
retour s;
Description du problème:
Actuellement, il y a des pièces avec des valeurs faciales de 2 Jiao 5 cents, 1 Jiao 5 cents, 5 cents et 1 cents.
Analyse des problèmes:
Selon le bon sens, lorsque nous allons au magasin pour acheter des choses et trouver de l'argent, le boss nous donne toujours la dénomination maximale en premier. Si le patron vous demande des scores ou quelques cents, vous ne le ferez certainement pas. En fait, c'est un problème typique du choix gourmand.
Conception d'algorithme et mise en œuvre du problème :
Permettez-moi d'abord de vous donner un exemple. Il le cherche comme ça? Je ne le fais pas, alors le patron ne peut que me donner que j'ai obtenu 3 25 points et on m'a donné 24 moins, donc j'ai dû me donner 2 10 points et 4 1 points.
La copie de code est la suivante:
// arithmétique pour trouver le changement
// Entrée: tableau M, stockez le nombre de valeurs faciales disposées de grande à petite en séquence.
// Sortie: Num du tableau, comparez le nombre de pièces avec différentes valeurs de dénomination dans le tableau M et trouvez un plan monétaire
public static int [] zhaoqian (int m [], int n)
{
int k = M.Length;
int [] num = new int [k];
pour (int i = 0; i <k; i ++)
{
num <i> = n / m <i>;
n = n% m <i>;
}
retour num;
}
La copie de code est la suivante:
classe publique Zhaoqian
{
public static void main (String [] args)
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [M.Length];
num = zhaoqian (m, n);
System.out.println (N + "Plan d'attente en argent:");
pour (int i = 0; i <M.Length; i ++)
System.out.println (num <i> + "zip" + m <i> + "valeur nominale");
}
public static int [] zhaoqian (int m [], int n)
{
int k = M.Length;
int [] num = new int [k];
pour (int i = 0; i <k; i ++)
{
num <i> = n / m <i>;
n = n% m <i>;
}
retour num;
}
}
Ce qui précède est tout le contenu de cet article, j'espère que vous pourrez l'aimer.