10/31 - Hotul

Solutia I. Hotul are un rucsac cu care poate cara o greutate maxima G. Exista n obiecte carora li se cunoaste greutatea si valoarea. Sa se determine obiectele de valoare maxima <=G.

#include<iostream>
#include<fstream>
using namespace std;
int n,i,G[100],V[100],S[100],REZ[100];
int greutate,vmax;
void afis(int n, int s, int v)
{int k;
for (k=1;k<=n;k++)
cout<<S[k]<<" ";
cout<<"--"<<s<<"--"<<v<<endl;
}

void afiseaza ()
{
for (i=1;i<=n;i++)
if (REZ[i]!=0)
cout<<REZ[i]<<" ";
cout<<" ->> "<<vmax<<endl;
}

void back(int i, int s, int v)
{
int j,k;
for (j=0;j<=1;j++)
{
S[i]=j;
s=s+j*G[i];
v=v+j*V[i];
if (i==n)
{
afis(i,s,v);
if (s<=greutate)
if (v>vmax)
for (k=1;k<=n;k++)
{
REZ[k]=S[k]*V[k];
vmax=v;
}
}
else
if(s<greutate) back(i+1,s,v);
}
}

int main()
{
ifstream fin("rucsac.in");
fin>>n>>greutate;
vmax=-1;
for (i=1;i<=n;i++)
fin>>G[i]>>V[i];
back(1,0,0);
afiseaza();
return 0;
}

Fisier

6 10
3 7
3 4
1 2
1 9
2 4
1 5

Solutia II. Hotul are un rucsac cu care poate cara o greutate maxima G. Exista n obiecte carora li se cunoaste greutatea si valoarea. Sa se determine obiectele de valoare maxima <=G. 

#include<iostream>
#include<fstream>
using namespace std;
int main()
{
int val=0,gr=0,j,V[100],G[100],i,n,greutate,p;
ifstream fin("rucsac.in");
cin>>n>>greutate;
for(i=1;i<=n;i++)
    cin>>G[i]>>V[i];

for(i=1;i<=n;i++)
{    for(j=i+1;j<=n;j++)
        {if(V[j]>V[i])
            {swap(G[i],G[j]);
            swap(V[i],V[j]);}
        if(V[j]==V[i])
            if(G[j]<G[i])
                {swap(G[i],G[j]);
                swap(V[i],V[j]);}
        }
}
      
for(j=1;j<=n;j++)
{
gr=gr+G[j];
if(gr>greutate)
    p=j;
}

for(i=1;i<p;i++)
{val=val+V[i];
cout<<G[i]<<" "<<V[i]<<endl;
}

cout<<"Valoare maxima: "<<val;
return 0;
}

Fisier

6 10
3 7
3 4
1 2
1 9
2 4
1 5