Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Problema Bancnotelor
58
Problema bancnotelor
Holcan Cosmin
Pelcear Cristian
Poleuca Raluca
Grigorescu Claudiu
Enunț
Având la dispoziție n (1<=n<=20) tipuri de bancnote, fiecare tip în număr nelimitat, să se afle numărul minim de bancnote ce pot fi utilizate pentru a plăti o sumă S<=3000. Se știe că se dispune de bancnota de o unitate.
Enunt
Programare dinamica
#include <iostream>
#include <algorithm>
using namespace std;
int suma[3000],bancnota[20], n, S, sol[3000];
void plata()
{
int i, j;
suma[0]=0;
for (j=1;j<=S;j++)
{
suma[j] =4000;
for (i=1;i<=n;i++)
if (bancnota[i] <= j && 1+suma[j - bancnota[i]]<suma[j])
{
suma[j]=1+suma[j - bancnota[i]];
sol[j]=bancnota[i];
}
}
cout <<"Numarul minim de bancnote: "<<suma[S]<<endl;
}
void constructSol(int k)
{
if (k > 0)
{
constructSol(k - sol[k]);
cout<<sol[k]<<" ";
}
}
int main()
{
cout << "n= ";
cin >> n;
cout << "S= ";
cin >> S;
for (int i=1;i<=n;i++)
{
cout <<"bancnota["<< i <<"]=";
cin >>bancnota[i];
}
plata();
cout <<"Bancnotele selectate: ";
constructSol(S);
return 0;
}
n=4 S=7
bacnota[1]=1
bancnota[2]=3
bancnota[3]=5
bancnota[4]=10
Noi trebuie sa determinăm suma[7]. Pentru aceasta vom determina suma[0], suma[1], suma[2], … ,suma[7].
Evident suma[0]=0;
Pentru a determina suma[1] : suma[1]=4000 initial (suma noastra e mai mica decat 3000 deci vom initializa suma[1] cu o valoare mai mare)
i=1 : suma[1]=1+suma[1-1]=1; sol[1]=1;
pentru i de la 2 la 4 bancnota[i]>j
Acum vom determina suma[2]
suma[2]=4000;
i=1 : suma[2]=1+suma[1]=2; sol[2]=1;
pentru i de la 2 la 4 bancnota[i]>j
j=3 => suma[3]=4000;
i=1 : suma[3]=1+suma[3-1]=1+suma[2]=3; sol[3]=1;
i=2 : suma[3]=1+suma[3-bancnota[2]]=1+suma[3-3]=1; sol[3] = 2;
pentru i de la 3 la 4 avem bancnota[i]>j
j=4 => suma[4]=4000;
i=1 : suma[4]= 1+suma[3]=1+1=2; sol[4]=1;
pentru i=2 1+suma[4-bancnota[2]]=suma[4]=2 iar pentru i de la 3 la 4 avem bancnota[i]>j
astfel suma[5]=1; sol[5]=3; suma[6]=2; sol[6]=1; suma[7]=3; sol[7]=1
Pentru a construi solutia : k=7 => constructsol(7-1) si retinem pe stiva 1 => constructsol(6-1) si retinem pe stiva 1 => constructsol(5-5) si retinem pe stiva 5 => constructsol (0) deci afiseam 5 1 1
Metoda Greedy
#include<iostream>
using namespace std;
int n,i,j,aux,s,a[100];
main()
{
cout<<"Suma=";cin>>s;
cout<<"Numarul de bancnote:";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]=";cin>>a[i];
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
if(a[i]<a[j])
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
}
i=1;
cout<<s<<endl;
do
{
if(s/a[i]>0)
cout<<s/a[i]<<" bancnote cu valoarea "<<a[i]<<endl,s=s%a[i];
i++;
}
while(i<=n);
return 0;
}
Pentru suma s=67 si bancnote de 1, 5, 10, 50, 100 lei
i=1 s/a[i]=67/100=0
i=2 s/a[i]=67/50=1 => 1 bancnota cu valoarea de 50 de lei si s devine 67%50=17
i=3 s/a[i]=17/10=1 => 1 bancnota cu valoarea de 10 lei si s devine 17%10=7
i=4 s/a[i]=7/5=1 => 1 bancnota cu valoarea de 5 lei si s devine 7%5=2
i=5 s/a[i]=2/1=2 => 2 bancnote cu valoarea de 1 leu