#include <iostream>
#include <math.h>
using namespace std;
//Declara struct de tip obiect_rucsac
struct obiect_rucsac {
int id; //Indicele din vectorul initial
int gi; //Greutatea unui obiect
int ci; //Castigul unui obiect
};
//Comparator pentru obiect_rucsac ( ordonare descrescatoare dupa ci/gi )
bool comparator_obiecte(obiect_rucsac a, obiect_rucsac b) {
return float(a.ci) / a.gi > float(b.ci) / b.gi;
}
//Functie QuickSort pentru ordonare vectori de orice tip.
template<typename Obj>
void quickSort(Obj arr[], int left, int right, bool (*comp)(Obj, Obj)) {
int i = left, j = right;
int tmp;
Obj pivot = arr[(left + right) / 2];
while (i <= j) {
while (comp(arr[i], pivot))
i++;
while (comp(pivot, arr[j]))
j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
};
if (left < j)
quickSort(arr, left, j, comp);
if (i < right)
quickSort(arr, i, right, comp);
}
//Functie pentru citirea datelor obiectelor
obiect_rucsac* citire_date(int& n) {
//Citire dimensiune
cout << "Introduceti numar obiecte : ";
cin >> n;
//Alocare dinamica vector de obiecte_rucsac
obiect_rucsac* v = new obiect_rucsac[n];
//Citire vector
cout << "\nIntroduceti greutate, castig pentru fiecare obiect :";
for (int index = 0; index < n; index++) {
cout << "\nObiect id #" << index << " : ";
v[index].id = index;
cin >> v[index].gi >> v[index].ci;
}
return v;
}
int main() {
int gmax, n;
//Citire greutate maxima
cout << "Introduceti greutate maxima rucsac : ";
cin >> gmax;
//Citire vector obiecte
obiect_rucsac* v = citire_date(n);
//Sortare obiecte descrescator dupa raportul ci/gi (folosind functia comparator declarata)
quickSort(v, 0, n - 1, comparator_obiecte);
int index = 0;
//Cat timp avem loc in ghiozdan si obiecte de pus
while (gmax > 0 && index < n) {
//Verifica daca obiectul incape complet in ghiozdan
if (v[index].gi <= gmax) {
//Pune in ghiozdan
cout << "\nDin obiectul cu id #" << v[index].id << " luam 100%";
//Actualizeaza locul ramas in ghiozdan
gmax -= v[index].gi;
//Treci la obiectul urmator
index++;
}
else {
//Daca obiectul nu incape complet in ghiozdan spune ce procent din acesta incape
cout << "\nDin obiectul cu id #" << v[index].id << " luam " << float(v[index].gi) / gmax << "%";
//Actualizeaza locul ramas in ghiozdan
gmax = 0;
}
}
}
Problema rucsacului este o problema specifica metodei Greedy. In metoda greedy alegem succesiv cea mai buna varianta la nivel local pentru a ajunge in final la cea mai buna varianta la nivel global.
In cazul nostru, cea mai buna varianta la nivel local este alegerea de fiecare data a obiectului care are cel mai bun raport [tex]\frac{castig}{greutate}[/tex].
Pentru a eficientiza determinarea acestui raport vom sorta vectorul de obiecte descrescator dupa acest raport (am folosit sortare quicksort aici dar poti folosi orice tip de sortare doresti, inclusiv sort-ul din <algorithm>).
Punem obiecte in rucsac in ordinea data de sortare. Exista trei posibilitati :
