BACKTRACKING REFERAT SCOALA

Se dau n tipuri de monezi.Sa se plateasca o suma data s,folosind un numar minim de monezi din tipurile date.Se considera ca exista un numar sufficient de monezi dn fiecare tip. Comentariu: Procedura rec primeste ca parametru un tip de moneda si incearca sa-l foloseasca pentru plata sumei ramase pana la momentul current,pornind de la numarul maxim de monezi pe care il poate folosi si pana la 0,procedura apelandu-se recursive pentru moneda urmatoare. program factura; const nmax=100; var i,n,s:byte; a,b,bm:array[1..nmax] of byte; nr,nrm:byte; procedure rec(x:byte); var i:integer; begin if nr<=nrm or nrm=0 then begin if x>n then begin if s=0 and nr<=nrm or nrm=o then begin bm:=b; nrm:=nr; end; end else for i:=s div a[x] downto 0 do begin s:=s-a[x]*i; b[x]:=i; nr:=nr+i; rec(x+1); s:=s+a[x]*i; nr:=nr-i; end end; end; begin write(‘intoduceti numarul de tipuri de monezi:’);readln(n); writeln(‘introduceti valorile monezilor:’); for i:=1 to n do read( a[i]); write(‘introduceti suma de platit:’);readln(s); nr:=0; nrm:=0;rec(1); if nrm=0 then begin if s=0 then writeln(‘factura nu trebuie platita’) else writeln(‘nu se poate plati suma data’); end else begin writeln(‘numarul minim de monezi este:’,nrm); for i:=1 to n do if bm[i]<>0 then writeln (bm[i],’monezi de ‘,a[i], ‘ lei’); end end.