J'ai un algorithme gourmand que je soupçonne peut-être correct, mais je ne suis pas sûr. Comment vérifier si c'est correct? Quelles sont les techniques à utiliser pour prouver un algorithme gourmand correct? Existe-t-il des modèles ou des techniques communs? J'espère que cela deviendra une question...
Étant donné un ensemble de pièces de monnaie de dénominations différentes et une valeur v, vous voulez trouver le moins de pièces nécessaires pour représenter la valeur v.c 1 , . . . , c nc1,...,cnc1, ... , cn Par exemple, pour le jeu de pièces 1,5,10,20, cela donne 2 pièces pour la somme 6 et 6...
Dans un premier temps , matroïdes ont été introduites pour généraliser les notions d'indépendance linéaire d'une collection de sous - ensembles sur un terrain mis . Certains problèmes qui contiennent cette structure permettent aux algorithmes gourmands de trouver des solutions optimales. Le concept...
On vous donne n entiers tous compris entre et . Sous chaque entier vous devez écrire un entier entre 0 et l avec la condition que les b i forment une séquence non décroissante. Définissez la déviation d'une telle séquence comme étant . Concevez un algorithme qui trouve les b_i avec l'écart minimum...
Il existe un algorithme gourmand pour trouver la couverture minimale des sommets d'un arbre qui utilise la traversée DFS. Pour chaque feuille de l'arbre, sélectionnez son parent (c.-à-d. Que son parent est dans la couverture de sommet minimum). Pour chaque nœud interne: si l'un de ses enfants n'est...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
J'ai une requête complexe utilisée pour rechercher un ensemble de données pour trouver . Chaque requête prend un temps moyen donc le temps global dans la recherche linéaire est. Je peux décomposer une requête en sous-requêtes plus simples q_i et trouver H_ \ text {approx} = \ {s \ in S \ mid \...
J'ai récemment discuté avec un ami d'un site Web qui proposait des défis d'expression régulière, correspondant principalement à un groupe de mots avec une propriété spéciale. Il cherchait une expression régulière qui correspond à des chaînes comme ||||||||où le nombre de |est premier. Je lui ai...
Étant donné un ensemble de n travaux avec [heure de début, heure de fin, coût], trouvez un sous-ensemble de sorte qu'aucun travail ne se chevauche et que le coût soit maximum. Maintenant, je ne sais pas si un algorithme gourmand fera l'affaire. C'est-à-dire, trier par coût et toujours prendre le...