Question

Salut! Am nevoie de o problema enuntata de noi rezolvata prin 2 metode. O data cu backtracking simplu si o data cu metoda greedy.

Answer 1

     Se efectueaza plata undei sume s utilizand un numar minim de monezi. Se cunosc valorile monezilor.
#include<iostream>
using namespace std;
int n,i,man,inv,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];
    }
    do
    {
        inv=0;
        for(i=1;i<=n-1;i++)
        if(a[i]<a[i+1])
        {
            man=a[i];
            a[i]=a[i+1];
            a[i+1]=man;
        }
    }
    while(inv);
    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);
}