Pagini recente » Cod sursa (job #2749784) | Cod sursa (job #2478561) | Cod sursa (job #527164) | Cod sursa (job #2385204) | Cod sursa (job #372031)
Cod sursa(job #372031)
/* Se dau n obiecte cu valoare si greutate cunoscuta.
se cunoasca greutatea max care poate fi carata.
Sa se aleaga obiecte a.i. valoarea totala sa fie maxima*/
#include<iostream>
#include<fstream>
using namespace std;
FILE * fin, * fout;
int v[100], c, n, g[100], p[100];
void read()
{
fin=fopen("rucsac.in","r");
fscanf(fin,"%d %d", &n, &c);
int i;
for(i=1;i<=n;i++)
{
fscanf(fin,"%d",&v[i]);
p[i]=i;
}
for(i=1;i<=n;i++)
fscanf(fin,"%d",&g[i]);
fclose(fin);
}
int schimb(int i,int j)
{
return v[p[i]]*g[p[j]]<g[p[i]]*v[p[j]];
}
void sort(int st, int dr)
{
if(st<dr)
{
int d=(st+dr)/2, i=st, j=dr, aux;
aux=p[d];
p[d]=p[st];
p[st]=aux;
while(i<j)
{
if(schimb(i,j))
{
aux=p[i];
p[i]=p[j];
p[j]=p[i];
d=1-d;
}
i+=d;
j-=1-d;
}
sort(st,i-1);
sort(i+1,dr);
}
}
void write()
{
fout=fopen("rucsac.out","w");
int i,s;
for(i=1,s=0;i<=n,s+g[i]<c;i++)
{
fprintf(fin,"%d",p[i]);
s+=g[p[i]];
}
fclose(fout);
}
int main()
{
read();
sort(1,n);
write();
return 0;
}