}
==

h1. Problema fractionara a rucsacului
 
Se considera ca dispunem de un rucsac cu capacitatea M si de N obiecte, definite fiecare prin greutate si valoare, ce trebuie introduce in rucsac. Se cere o modalitate de a umple rucsacul cu obiecte , astfel incat valoarea totala sa fie maxima. Este posibil ca oricate obiecte si bucati din obiecte sa fie introduse.
 
h2. Date de intrare
 
Pe prima linie a fisierului de intrare _rucsac.in_ se gasesc doua numere, primul fiind N, iar al doilea M (cu specificatiile din enunt). Pe urmatoarele N linii se gasesc, despartite printr-un spatiu greutatea obiectului curent si valoarea acestuia.
 
h2. Date de iesire
 
In fisierul de iesire _rucsac.out_ vor fi specificate numarul de ordine al obiectului, precum si procentul in care acesta poate fi introdus in rucsac.
 
h2. Exemplu
 
|_. rucsac.in | |_. rucsac.out |
| 5 100
1000 120
500 20
400 200
1000 100
25 1|          | 2 100
                 4 79
                 5 100 |
 
h2. Descrierea solutiei
 
Vom reprezenta solutia problemei ca pe un vector x. Vom ordona obictele descrescator tinand cont de valoarea/greutate. Atata timp cat obiectele incap in rucsac, le vom adauga in intregime. Completam rucsacul cu un fragment din urmatorul obiect ce nu a fost deja selectat.
 
O implementare simpla a acestui algoritm este urmatoarea:
 
 
==code(cpp) |
 
#include <iostream>
#include <fstream>
using namespace std;
 
ifstream f("rucsac.in");
ofstream g("rucsac.out");
 
int o[100],N,M;
float val[100],greu[100],x[100],Gr;
 
void  citeste()
{
	int i;
	f>>N>>M;
	for (i=0;i<N;++i)
	{
		o[i]=i;
		f>>val[i]>>greu[i];
	}
	f.close();
}
 
void sort()
{
	int i,aux,schimb;
	do
	{
		schimb=0;
		for (i=0;i<N-1;++i)
			if (val[o[i]]/greu[o[i]]<val[o[i+1]]/greu[o[i+1]])
			{
				aux=o[i];
				o[i]=o[i+1];
				o[i+1]=aux;
				schimb=1;
			}
	}
	while (schimb);
}
 
void rezolva()
{
	int i;
	for (i=0,Gr=M;i<N && Gr>greu[o[i]];++i)
	{
		x[o[i]]=1;
		Gr-=greu[o[i]];
	}
}
 
void afisare()
{
	int i;
	for (i=0;i<N;++i)
		if (x[i]) g<<i+1<<" "<<x[i]*100<<endl;
	g.close();
}
 
int main()
{
	citeste();
	sort();
	rezolva();
	afisare();
	return 0;
}
 
==