Dobry wieczór,
Piszę bankomat, i dotarłem do problemu wydawania reszty. Wyważyłem otwarte drzwi, napisałem swój algorytm (zachłanny), który w miarę działa (podaje liczbę i nominał banknotów do wypłaty aby osiągnąć zadaną kwotę). Niestety tylko w miarę, gdyż leży wydawanie kwoty 60 zł mając do dyspozycji banknoty 20 i 50 zł. Znalazłem dynamiczny algorytm, który podobno rozwiązuje niedogodności na które natrafiłem. Jednak im dłużej go analizuję, tym bardziej dochodzę do wniosku że ten algorytm mówi jedynie jaka jest najmniejsza liczba banknotów którą da się wypłacić zadaną kwotę. Nie mówi natomiast w jakich ilościach poszczególnych banknotów należy użyć. Czy da się wyciągnąć tą informację (ile jakich banknotów użyć) z tego algorytmu ?
#define INFINITY 2147483647 // nieskończoność definiujemy umownie jako górny kres typu integer
#include
using namespace std;
void main (void)
{
int a=3;
int k=13;
// a – liczba nominałów, k – żądana kwota
int* T= new int[k+1]; // utwórz tablicę T o zakresie od 0 do k
T[0] = 0; // dla kwoty 0 potrzebujesz 0 monet
int i;
for (i=1;i<=k;++i) // dla każdej kwoty od 1 do k
T[i]=INFINITY; // potrzebujesz nieskończoność monet
for (i=1;i<=a;++i) // dla każdego nominału wykonuj:
{
int n; // n – aktualnie analizowany nominał
cin >> n; // wczytaj nominał
for (int j=0;j<=k-n;++j) // dla j=0 do k-n wykonuj:
if (T[j] < INFINITY) // jeżeli T[j] już ma przypisaną wartość i jeżeli
if (T[j]+1 < T[j+n]) // dodanie monety zmniejszy liczbę monet dla kwoty j+n,
T[j+n] = T[j]+1; // to zapisz nową liczbę monet dla zwiększonej kwoty.
for (int z=0;z<=k;++z){
cout<
}
cout<
}
system("pause");
}
Mój kompilator to VisualStudio 2010, System Windows 7, aczkolwiek wątpię iż w tym przypadku ma to jakiekolwiek znaczenie.