Changement de monnaie : quels sont les sous-problèmes qui se chevauchent ?

Question

Voici la source du problème à uva.onlinejudge.org

Le problème est essentiellement le suivant :
Etant donné N montant d'argent qui doit être donné, nous devons trouver le nombre minimum de pièces que nous pouvons donner et la valeur totale de ces pièces pour que le montant supplémentaire donné soit minimal en utilisant n dénominations données.

Par exemple :

1400 -> N 
3    -> no of denominations 
500 
1000 
2000

Output: 1500 2

Ma question est la suivante :
Quels sont les sous-problèmes qui se chevauchent ?

Je veux dire.. :
Existe-t-il des sous-problèmes qui se chevauchent ?
Parce que je n'ai pas trouvé de...

Answer 1

Les sous-problèmes qui se chevauchent consistent à déterminer le nombre minimum de pièces/billets dont la somme est égale à un certain nombre de centimes.

for coin_value in coins(sorted)
   for sum where num[sum] is valid
      num[ sum + coin_value ] = Min( num[sum + coin_value], num[sum] + 1 )

Voir : Programmation dynamique Changement de monnaie Pièces limitées

Les contraintes du problème sont suffisamment faibles pour que l'on puisse utiliser la réponse acceptée à cette question. La seule différence est que vous calculez le nombre minimum de pièces/billets pour atteindre le prix cible, puis vous continuez à dépasser le prix cible. Lorsque vous avez fini de remplir le tableau, commencez par le prix cible et continuez jusqu'à ce que vous trouviez une réponse valable.

Triez les pièces/billets en commençant par la plus grosse dénomination et en descendant.

(Ma solution a été acceptée à l'UVa.)