Witajcie!
Uczę sie programować 2 miesiące, cały kurs z youtube(Mirosława Zelenta) już za mną, jednak niestety nadal często się gubie i tracę siły...
W tym wypadku poddałem się totalnie i potrzebuje pomocy.
Na zajęcia z Algorytmów i Struktur danych dostaliśmy zadanie stworzyć kase fiskalną.
Kasa ta ma pytać o swój stan>podliczyć sume>obsłużyć klienta wydając reszte w optymalny sposób.
No właśnie... optymalny. Na jednych zajęciach profesor już "zgasił" jednego z nas, ponieważ każdy z nas zrobił to zadanie algorytmem zachłannym, a pan profesor dał do kasy 50 zł, 3x 20zł i 10 razy po złotówce. Oczywiście algorytm zamiast użyć tylko 3 nominałów używał ich 11... Od poniedziałku walcze z problemem, rozumiem że musze rozwiązać ten problem dynamicznie, ale niestety po prostu nie umiem... Obejrzałem mase filmików na YouTube o problemie plecakowym itd. niestety nadal nie jestem w stanie poradzić sobie z problemem
Mój kod na ten moment wygląda tak
#include <iostream>
#include <cstdlib>
#include <conio.h>
#define INFINITY 2147483647
using namespace std;
struct Banknot {
string nazwa;
float wartosc;
int ilosc[15];
};
float Suma( Banknot kasa[], int n )
{
float suma = 0;
for( int i = 0; i < n; i++ )
{
suma += kasa[ i ].ilosc[i] * kasa[ i ].wartosc;
}
return suma;
}
int wpisz(Banknot kasa[], int n)
{
for(int i=0; i<n; i++)
{
cout<<"Ile banknotow warosci " << kasa[i].nazwa<<" ma byc w kasie"<<endl;
cin >> kasa[i].ilosc[i];
}
}
int SumaNom(Banknot kasa[],int iLiczb)
{
int SumaNom=0;
for (int i=0;i<iLiczb;i++)
{
SumaNom+=kasa[i].ilosc[i];
}
return SumaNom;
}
int main()
{
int ilosc[15];
Banknot kasa[ 15 ] = {
{ "500", 500, ilosc[0] },
{ "200", 200, ilosc[1] },
{ "100", 100, ilosc[2] },
{ "50", 50, ilosc[3] },
{ "20", 20, ilosc[4] },
{ "10", 10, ilosc[5] },
{ "5", 5, ilosc[6] },
{ "2", 2, ilosc[7] },
{ "1", 1, ilosc[8] },
{ "0.5", 0.5, ilosc[9] },
{ " 0.2", 0.2, ilosc[10] },
{ "0.1", 0.1, ilosc[11] },
{ "0.05", 0.05, ilosc[12] },
{ "0.02", 0.02, ilosc[13] },
{ "0.01", 0.01, ilosc[14]},
};
wpisz(kasa,15);
float suma=Suma(kasa,15);
int Sumanominalow=SumaNom(kasa,15);
cout << "w kasie jest : " << suma <<"PLN w "<<Sumanominalow<<" nominalach \n";
cout<<"ile pieniedzy wydajemy :) ?"<<endl;
float wydatek,reszta;
cin>>wydatek;
reszta=suma-wydatek;
cout<<"reszta to "<< reszta;
/*k – żądana kwota; według przykładu 13
n – największy element zbioru nominałów
x – liczba potrzebnych monet; początkowo 0
*/
int* T = new int[reszta+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<=reszta;++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.
}
}
}
}
*/
return 0;
}
Od chwili komentarzy jest moja walka z problemem, przy pomocy kodu z WIkipedii, niestety nawet nie wiem jak zaimplikować gotowca... Czy mógłby mi ktoś pomóc z problemem? Mam czas do piątku i obawiam się że sobie nie poradzę, tym bardziej że jutro czeka mnie nauka na kolokwium z Informatyki (na szczęście to tylko wstęp i materiał uważam za prosty)
