Dziel i zwyciężaj a problem kasjera

Witam,
Chciałbym prosić o radę odnośnie problemu kasjera przy pomocy metody dziel i zwyciężaj. W sumie nie wiem jak powinna wyglądać implementacja tego algorytmu przy pomocy tej klasy.
Zakładam resztę mniejszą niż 100gr - czyli mam do dyspozycji sześć monet - 1, 2, 5, 10, 20 oraz 50. Umieszczam je w tablicy 6-elementowej:

type
  mon = array[1..6] of byte;
  co  = array[1..6] of byte;
var
  monety: mon;
  c: co;

procedure wypelnij;
begin
monety[1]:=1;
monety[2]:=2;
monety[3]:=5;
monety[4]:=10;
monety[5]:=20;
monety[6]:=50;
end; 

Mam tutaj stworzoną też drugą tablicę, którą zamierzam wykorzystać do zliczania, ile monet i w jakich nominałach "kasjer" ma wydać.
I w przypadku dziel i zwyciężaj, wiem że mam skorzystać z rekurencji, aby podzielić problem na mniejsze. Ale na co tutaj mam podzielić? Proszę o jakieś rady. W między czasie postaram się też samemu do czegoś dojść.

A musisz tu używać dziel i zwyciężaj? Bo problem wydawania reszty to jest problem programowania dynamicznego...
Stosując metodę dziel i zwyciężaj możesz uzyskać rozwiązania nieoptymalne po prostu. Przykład:
mamy do wydania 6zł
dzielimy to na pół więc mamy do wydania 3zł i 3zł, z tych podproblemów uzyskamy 1+2 oraz 1+2 czyli w efekcie 4 monety zamiast 2+2+2.
Możesz oczywiście przy zlączaniu rozwiązań podproblemów sprawdzać czy nie da się wymienić najniższych niminałów na jakiś większy, ale wydaje mi się to trochę pokrętnym rozwiązaniem.

Właśnie jest taki problem że na zajęciach mamy do porównania metodę dziel i zwyciężaj oraz właśnie wersję dynamiczną. Chcę się przygotować zarówno do tej pierwszej jak i drugiej metody. I mam problem, bo "ugrzązłem" na dziel i zwyciężaj - albo mój program wybiera właśnie złą resztę, albo się zapętla.
Z tego co myślałem to dziel i zwyciężaj do sortowania czy wyszukiwania elementów jest wykorzystywany, a nie do tego.

function kasjer(reszta: byte; var c: co): byte;
var
  i,j,k,max,temp : byte;
  ct: co;
begin
if reszta = 0 then begin
  for i:=1 to 6 do c[i]:=0;
  kasjer:=0;
end else
begin
     max:=255;
     for j:= 1 to 6 do if reszta - monety[j] >= 0 then begin
       temp:=kasjer(reszta-monety[j], ct)+1;
       if max >= temp then begin
         max:=temp;
         writeln(max);
         for i:=1 to 6 do c[i]:=ct[i];
         c[j]:=c[j]+1;
       end;
       kasjer:=max;
     end;

end;
end; 

Co tutaj może być źle?

Edytowane: Z tego co widzę i przemyślałem to ten mój algorytm nie jest chyba wykonany jako dziel i zwyciężaj.
Co do wyników tego algorytmu to dla małych wartości dobrze działa, dla większych (powyżej 20) program się zapętla.

Istnieją pewne teoretyczne warunki kiedy metody dynamiczne i kiedy metody dziel i zwyciężaj są poprawne.
Dla programowania dynamicznego jest warunek optymalnej podstruktury, dla dziel i zwyciężaj jest to trochę ostrzejszy warunek -> problem musi mieć własność optymalnej podstruktury ale dla rozłącznych podproblemów. Moim zdaniem w przypadku wydawania reszty ten warunek spełniony nie jest, bo tak jak podawałem wyżej: rozwiązane optymalne nie jest funkcją optymalnych rozwiązań rozłącznych podproblemów.

Zawsze możesz zrobić coś w rodzaju:

wydaj(X):
    if istnieje moneta/banknot o wartości X:
        reurn [X]
    else:
        pierwsza_połowa = wydaj(X/2)
        druga_połowa = wydaj((X+1)/2) # to +1 żeby dobrze działało dla nieparzystych
        return połącz(pierwsza_połowa, druga_połowa)

Problem będzie sprawiała implementacja funkcji połącz. Jesli rozwiązanie ma być optymalne, musi łączyć monety o mniejszych nominałach w większe.
Napisanie tego sensownie będzie wymagało trochę uwagi, ale zakładając że wydaj() zwraca posortowaną listę (proste do zapewnienia), można to prawdopodobnie napisać w czasie liniowym.
Tzn. połącz([1, 2, 5], [2, 2, 5]) najpierw robi merge posortowanych list (otrzymując [1, 2, 2, 2, 5, 5]) a później łączy po kolei otrzymując [2, 5, 10].

PS. zadanie napisania tego za pomocą dzielenia i zwyciężania oczywiście bezsensowne

Czy nie wystarczy to:

type  Division=array[0..5] of Word;
const Mon:Division=(1,2,5,10,20,50);

function kasjer(Value:Word):Division;
var I:Integer;
begin
  for I:=High(Result) downto Low(Result) do
  begin
    Result[I]:=Value div Mon[I];
    Dec(Value,Result[I]*Mon[I]);
  end;
end;