Excel/PowerQuery - Trouver les combinaisons correspondant à une valeur cible, approche optimisée ...

Dans cette vidéo *Excel – Power Query* , nous abordons un problème combinatoire avancé : trouver des combinaisons de montants permettant d’atteindre une valeur cible. Une vidéo sur ce sujet a déjà été réalisée il y a quelques mois ( https://youtu.be/pRZGmpRCCgc?si=sSuOpxvJmXAGJOKk ), mais les solutions proposées sous Power Query, étaient limitées à trouver une combinaisons parmi une vingtaine de valeurs. Cette fois, plutôt que d’utiliser une approche générant toutes les combinaisons possibles (complexité exponentielle) , nous mettons en œuvre une approche optimisée : *Meet in the Middle* qui nous permettra de traiter jusqu’à *35* valeurs dans des conditions acceptables. Cette méthode consiste à : • Diviser la liste initiale en deux sous-ensembles • Générer les combinaisons de chaque moitié séparément • Calculer les sommes partielles associées • Mettre en correspondance les deux blocs afin d’identifier les couples de combinaisons atteignant la somme cible. Principales fonctions Power Query (langage M) utilisées : *List.Accumulate* pour la génération progressive des combinaisons *List.Transform* pour appliquer des transformations aux listes *List.Combine* pour combiner les listes *List.Buffer* et *Table.Buffer* pour optimiser le traitement Fichier source : https://gofile.io/d/Gkc7Jy