Ajutor va rog urgent in c++ dar sa explicati cum functionezaa programul pe pasi
O persoană are un rucsac cu care poate transporta unul sau mai multe obiecte, greutatea sumară a cărora nu depăşeşte valoarea Gmax. Pentru fiecare obiect i (i =1,2,…,n) se cunoaşte greutatea gi şi câştigul ci care se obţine în urma transportului său la destinaţie. În ipoteza că unele obiecte pot fi tăiate în fragmente mai mici, elaboraţi un program care determină ce obiecte i alege persoana şi în ce proporţie xi le ia astfel încât câștigul total să fie maxim şi să nu se depășească greutatea maximă a rucsacului.
Răspunsuri la întrebare
RASPUNS C++:
#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;
}
}
}
EXPLICATIE :
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 .
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 :
- Obiectul index incape complet in rucsac, moment in care trecem la obiectul index+1
- Obiectul index nu incape complet in rucsac, moment in care introducem in rucsac proportia maxima din acest obiect care incape. Dupa aceasta operatie rucsacul este plin si algoritmul se termina
- Am introdus toate obiectele in ghiozan si inca mai avem loc liber. In acest caz algoritmul se termina.