Problem frakcijskog naprtnjače u C++ odnosi se na identificiranje načina za punjenje vrećice predmetima zadane težine i profita na takav način da vrećica sadrži maksimalnu vrijednost bez prekoračenja maksimalnog ograničenja.
Kako riješiti problem frakcijskog naprtnjače u C++
Zadani skup predmeta, od kojih svaki ima zadanu težinu i dobit, odredite svaki broj predmeta u takvoj kombinaciji da ukupna težina predmeta bude manja od maksimalnog ograničenja vreće, ali vrijednost mora biti što veća.
Algoritam za implementaciju problema frakcijskog naprtnjače
Funkcioniranje algoritma Knapsack može se razumjeti kroz sljedeće točke:
- Uzmite dva niza težine i profita.
- Postavite maksimalnu vrijednost vreće na W.
- Odredite gustoću uzimajući omjer oba parametra.
- Poredaj stavke u padajućem redoslijedu prema gustoći.
- Zbrajajte vrijednosti dok ne bude <=W.
Pohlepni pristup rješavanju problema frakcijskog naprtnjače
Pohlepni pristup ima za cilj napraviti idealne izbore u svakom koraku, što dovodi do idealnog rješenja na kraju. Rješava probleme korak po korak vodeći do zaključaka umjesto da rezultate zaključi samo na kraju. Ovo je izvorni kod za implementaciju rješenja problema frakcijskog naprtnjače u C++:
#include
korištenjem imenski prostor std ;
strukturirati Objekt {
int vrijednost, težina ;
Objekt ( int vrijednost, int težina )
: vrijednost ( vrijednost ) , težina ( težina )
{
}
} ;
bool cmp ( strukturirati Objekt x, strukturirati Objekt y )
{
dvostruko A1 = ( dvostruko ) x. vrijednost / x. težina ;
dvostruko A2 = ( dvostruko ) i. vrijednost / i. težina ;
povratak A1 > A2 ;
}
dvostruko fractionalNaprtnjača ( strukturirati Objekt arr [ ] ,
int U, int veličina )
{
vrsta ( arr, arr + veličina, cmp ) ;
int curWeight = 0 ;
dvostruko konačna vrijednost = 0,0 ;
za ( int ja = 0 ; ja < veličina ; ja ++ ) {
ako ( curWeight + arr [ ja ] . težina <= U ) {
curWeight + = arr [ ja ] . težina ;
konačna vrijednost + = arr [ ja ] . vrijednost ;
}
drugo {
int ostati = U - curWeight ;
konačna vrijednost + = arr [ ja ] . vrijednost
* ( ( dvostruko ) ostati
/ arr [ ja ] . težina ) ;
pauza ;
}
}
povratak konačna vrijednost ;
}
int u = 60 ;
Objekt arr [ ] = { { 100 , dvadeset } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int veličina = veličina ( arr ) / veličina ( arr [ 0 ] ) ;
cout << 'Maksimalni profit = '
<< fractionalNaprtnjača ( arr, v, veličina ) ;
povratak 0 ;
}
U ovom kodu definirana je struktura objekta koja ima pohranjene vrijednosti težine i dobiti. Bool cmp() se koristi za usporedbu između dva objekta na temelju omjera težine i vrijednosti dvaju objekata. Niz je raspoređen silaznim redoslijedom i vrijednost se nastavlja dodavati dok ne dosegne maksimum. Ako je trenutna vrijednost dopuštena i unutar ograničenja, dodaje se, u protivnom se njen smanjeni omjer dodaje u vrećicu. Veličina težine i vrijednosti unosi se u glavni kod, a maksimalna dobit ispisuje se na izlazu.
Maksimalni profit koji je pohranjen u snacku je 580.
Zaključak
Problem frakcijskog naprtnjače u C++ odnosi se na identificiranje načina za punjenje vrećice predmetima zadane težine i profita na takav način da vrećica sadrži maksimalnu vrijednost bez prekoračenja maksimalnog ograničenja. To se može postići pohlepnim pristupom koji ima za cilj napraviti idealne izbore u svakom koraku, što na kraju dovodi do idealnog rješenja.