Algorithme récursif pour l'itinéraire budgétisé

Question

J'essaie de résoudre un problème récursif. Cependant, ne pas arriver à une solution de travail. Lorsque je travaille avec des problèmes récursifs, je commence généralement par faire un itératif puis le convertir, mais dans ce cas, je n'ai pas pu le faire ...

L'entrée est une liste de n éléments donnés par leur prix à l'unité de le moins cher au plus cher, et une valeur de budget; tous les entiers positifs.

method(int unitPriceList[], int budget) 
Unit Price List = [ 3 , 7 , 9 ]. Budget = 18 

Les impressions de sortie tous les itinéraires possibles saturés comme une liste des quantités d'articles, une liste par ligne, chacune suivie par son prix total sur la même ligne. Le terme «saturé» signifie que c'est dans les limites du budget, mais il ne sera pas dans les limites du budget si nous y ajoutons d'autres éléments.

Quantities = [ 0 , 0 , 2 ]. Total Price = 18. 
Quantities = [ 1 , 2 , 0 ]. Total Price = 17. 
Quantities = [ 0 , 1 , 1 ]. Total Price = 16. 
... 
The number of saturated itineraries = … 

Je serais vraiment reconnaissant si vous pouviez me diriger dans la bonne direction pour résoudre ce problème.

Answer 1

Ce serait un cas du problème "toutes les combinaisons de pièces". Trouver une solution pour cela. Pour convertir à votre cas, ajoutez une pièce d'unité (Prix == 1). Maintenant, rejetez toute solution qui a autant de pièces unitaires que votre prix le moins cher (3 dans ce cas). En comparant, vous êtes à la recherche d'un nombre de façons de faire 18 cents avec des coupures de (1, 3, 7, 9) - mais vous ne pouvez pas utiliser plus de deux pièces de 1 cent. Cela nécessiterait de négocier dans ces pièces pour une dénomination plus élevée.

Est-ce que cela vous aide à bouger?