Sac à dos illimité et rendu de monnaie II

Dans le sac à dos non borné, chaque élément peut être pris un nombre quelconque de fois (contrairement au sac à dos 0/1, où chaque élément est utilisé au plus une fois). La définition de l’état reste la même — dp[c] = valeur maximale atteignable avec une capacité c —, mais le sens du parcours change. Comme les éléments sont réutilisables, lorsque nous mettons à jour dp[c], nous voulons permettre une nouvelle utilisation de l’élément courant ; nous parcourons donc la capacité de gauche à droite (vers l’avant).

Rappelez-vous que, dans le sac à dos 0/1, nous parcourions la capacité de droite à gauche pour empêcher la réutilisation. Dans le sac à dos non borné, nous faisons l’inverse : nous parcourons la capacité de gauche à droite. Lors du calcul de dp[c], dp[c-w] a déjà été mis à jour au cours du passage actuel ; cela signifie que l’élément i a peut-être déjà été inclus. C’est exactement ce que nous voulons : l’élément i peut être ajouté une nouvelle fois à une solution qui le contient déjà.

Le rendu de monnaie II demande, étant donné des valeurs de pièces et un montant, de compter le nombre de façons distinctes d’obtenir ce montant (chaque pièce peut être utilisée sans limite). Il s’agit d’une variante du sac à dos non borné dans laquelle, au lieu de maximiser une valeur, nous comptons les combinations. Définissez dp[c] comme le nombre de façons d’obtenir le montant c. Cas de base : dp[0] = 1 (une façon d’obtenir 0 : ne rien prendre).

Pour chaque pièce, parcourez les montants de gauche à droite et cumulez : dp[c] += dp[c - coin]. Le cas de base dp[0] = 1 initialise le décompte. Notez que la boucle externe porte sur les pièces et la boucle interne sur les montants : cela produit naturellement un décompte des combinations (et non des permutations), car chaque valeur de pièce est prise en compte exactement une fois lors d’un passage externe.

L’ordre des boucles est déterminant. Si nous plaçons le montant dans la boucle externe et la pièce dans la boucle interne, nous comptons des permutations (l’ordre compte). Pour amount=5 avec les pièces [1,2], 1+2+2 et 2+1+2 sont comptés séparément. Si nous plaçons la pièce dans la boucle externe, nous comptons des combinations (l’ordre ne compte pas) : 1+2+2 et 2+1+2 sont identiques. Le rendu de monnaie II demande des combinations ; la pièce doit donc être dans la boucle externe.

Autre problème classique du sac à dos non borné : étant donné une barre de longueur n et les prix correspondant à chaque longueur de barre de 1 à n, trouvez la recette maximale en découpant la barre de manière optimale. Chaque morceau de longueur l peut être vendu au prix price[l], et les morceaux peuvent être réutilisés (la barre peut être découpée en plusieurs morceaux de même longueur). Ce problème correspond directement au sac à dos non borné avec W = n, les éléments étant les différentes longueurs de découpe.

Le rendu de monnaie I (un problème différent) demande le nombre minimal de pièces nécessaires pour obtenir un montant cible. Ici, dp[c] = nombre minimal de pièces pour obtenir le montant c. Récurrence : dp[c] = min(dp[c], dp[c - coin] + 1). Initialisez toutes les entrées à inf, sauf dp[0] = 0. Ce problème est également non borné (les pièces peuvent être réutilisées), donc parcourez les montants de gauche à droite. Renvoyez dp[amount] si sa valeur est finie, sinon -1.

Les trois variantes du sac à dos non borné utilisent des opérations différentes sur dp[c-coin] : Maximiser la valeur : dp[c] = max(dp[c], dp[c-w] + v) ; initialisation à 0. Minimiser le coût : dp[c] = min(dp[c], dp[c-coin] + 1) ; initialisation à inf, dp[0]=0. Compter les façons : dp[c] += dp[c-coin] ; initialisation à 0, dp[0]=1. Reconnaître la variante applicable représente déjà la moitié du travail dans les problèmes d’entretien.

Toutes les variantes du sac à dos non borné s’exécutent en O(n × W) en temps et O(W) d’espace, où n est le nombre de types d’éléments et W le montant cible. Pour les problèmes de rendu de monnaie, n correspond au nombre de valeurs de pièces. En entretien, indiquez la variante (maximum, minimum ou décompte), écrivez la DP en 1D et précisez si la boucle externe porte sur les pièces ou sur le montant : les examinateurs savent que cette distinction permet d’évaluer une compréhension approfondie de la DP.

Utilisez les indications suivantes pour identifier la variante applicable : réutilisation illimitée → sac à dos non borné (parcours vers l’avant) ; chaque élément exactement une fois → sac à dos 0/1 (parcours en sens inverse) ; l’énoncé indique « un nombre quelconque de fois », « une quantité infinie » ou « la réutilisation est autorisée » → sac à dos non borné. Exemples : rendu de monnaie, découpe d’une barre, décomposition d’un entier — tous non bornés. Somme de sous-ensembles, partition, sac à dos 0/1 — problèmes 0/1. Se tromper sur ce point entraîne des réponses incorrectes difficiles à déboguer.

Décomposition d’un entier (LeetCode 343) : diviser un entier n en au moins 2 entiers positifs afin de maximiser leur produit. Il s’agit d’un sac à dos non borné dans lequel les « éléments » sont les entiers de 2 à n-1. Définissez dp[i] comme le produit maximal d’entiers dont la somme vaut i. Pour chaque élément j de 2 à i, dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Cela montre comment le schéma du sac à dos non borné se généralise au-delà du contexte du rendu de monnaie.

Évaluez votre compréhension des notions de structures de données et d’algorithmes — préparation aux entretiens de programmation — abordées dans cette leçon.

Dans cette leçon, vous avez appris : le sac à dos non borné parcourt la capacité de gauche à droite afin de permettre la réutilisation des éléments, le rendu de monnaie II compte les combinations en plaçant la pièce dans la boucle externe, et les trois variantes — maximiser, minimiser, compter — ne diffèrent que par l’opération appliquée à la DP et son initialisation. Ensuite, nous utiliserons le sac à dos 0/1 pour résoudre le problème de partition en sous-ensembles de somme égale.