Wydawanie reszty - problem z implementacją alg. dynamicznego


(Tabcin) #1

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.


(kostek135) #2

Nie zagłębiam się w to, bo nazwy zmiennych mnie dobijają i pętla zwiastuje rozwiązanie w czasie O(n), gdy można to zrobić O(1). Zakładam, że bankomat może mieć zleconą wypłatę 50 wzwyż (nie ma to wiekszego znaczenia, bo jeśli chodzi o inne wypłaty: jesteśmy w stanie dokonać tylko 40 złotych - jeden if na samym początku). Zakładam też, że chcemy zatrzymać jak najwięcej niższego nominału.

Masz kwotę x dzielisz ją przez 50, reszta z dzielenia może wynosić 0, 10, 20, 30, 40. Jeśli 0 lub 20 lub 40, to nie jest problem, resztę z dzielenia odejmujesz od kwoty x dzielisz przez 50 -> da ci to ilość banknotów 50 złotowych,i dodatkowo jeśli reszta 0 to 0 banknotów 20 złotowych, jeśli reszta 20 to 1 banknot 20 złotowy, jesli reszta 40 to 2 banknoty 20 złotowe. Przy 10 i 30, odejmujesz od x te kwote i jeszcze 50. to co zostanie x / 50 to ilosc banknotów 50 złotowych, a dodatkowo 20 złotowych będzie ((10 lub 30) + 50) / 20 -> czyli tak naprawdę dla 10 da ci zawsze 3 dla 30 -> 4;

Dla 60 zachowa się to tak

60 % 50 = 10

60 - 10 - 50 = 0

0/50 = 0 banknotów 50zł

(10 + 50) / 20 = 3 banknoty 20 zł.

Kilka dzieleń i już.


(Tabcin) #3

Dzięki, zobaczę jak to działa w praktyce i w razie problemów dam znać