mi się wydaję że wystarczy tyko zmodyfikować klasyczne rozwiązanie dynamiczne, potrzebujemy dodatkowej tablicy m x n do zapisania informacji ile razy skorzystaliśmy z danego nominału do obliczenia danej kwoty, a dalej już w klasycznym rozwiązaniu po prostu sprawdzać czy nie przekroczyliśmy limitu użycia danego nominału
Nie analizowałem dokładnie Twojego algorytmu, ale jeśli to jest jedyna modyfikacja względem algorytmu wydawania reszty, to nie będzie działać.
Tzn. będzie działać, ale nie będzie gwarantować optymalnych rozwiązań, ponieważ zadanie nie jest wtedy prawidłowo podzielone na etapy. Ba, może w ogóle nie znaleźć rozwiązania, mimo że istnieje.
Nie masz spełnionego warunku niezależności etapów, tzn. przyszłe stany są u Ciebie zależne od poprzednich, a to jest warunek konieczny dla działania programowania dynamicznego.
Przykładowo dla przedmiotów:
{3, 4, 4, 5} i pojemności 11 prawidłowym rozwiązaniem jest { 4, 4, 3 }.
Jednak dla etapu n = 8 wynik możesz skonstruować na 2 równoważne sposoby { 4, 4 } oraz { 5, 3 }. W klasycznym algorytmie wydawania reszty nie ma znaczenia, który ze sposobów wybierzesz, więc etap dla n= 8 jest całkowicie niezależny od kolejnych etapów i dlatego programowanie dynamiczne działa - właśnie poprzez redukcję tych wszystkich równoważnych przypadków do jednego. W klasycznym algorytmie wydawania reszty trójkę możesz powtórzyć, więc ostatecznie miałbyś 2 równoważne rozwiązania { 5, 3, 3 } oraz { 4, 4, 3 }. Jednak tutaj, jeśli wybierzesz { 5, 3 } to zabraknie Ci potrzebnego elementu w etapie dla n = 11 i algorytm zakończy się ze stwierdzeniem, że nie znaleziono rozwiązania, bo nie masz już drugiej trójki.