Problem frakcijskega nahrbtnika v C++ se nanaša na prepoznavanje načina za polnjenje vrečke s predmeti dane teže in dobička na tak način, da vrečka vsebuje največjo vrednost, ne da bi presegla največjo omejitev.
Kako rešiti problem frakcijskega nahrbtnika v C++
Glede na nabor predmetov, vsak z dano težo in dobičkom, določite vsako število predmetov v takšni kombinaciji, da bo skupna teža predmetov manjša od največje omejitve vreče, vendar mora biti vrednost čim večja.
Algoritem za implementacijo problema delnega nahrbtnika
Delovanje algoritma Knapsack je mogoče razumeti skozi naslednje točke:
- Vzemite dve nizi teže in dobička.
- Največjo vrednost vreče nastavite na W.
- Določite gostoto tako, da vzamete razmerje med obema parametroma.
- Predmete razvrstite po padajoči gostoti.
- Seštevajte vrednosti, dokler ni <=W.
Pohlepni pristop k reševanju problema frakcijskega nahrbtnika
Cilj pohlepnega pristopa je narediti idealne izbire na vsakem koraku, kar vodi do idealne rešitve na koncu. Težave rešuje korak za korakom in privede do sklepov, namesto da rezultate zaključi le na koncu. To je izvorna koda za implementacijo rešitve problema delnega nahrbtnika v C++:
#include
uporabo imenski prostor std ;
struct Objekt {
int vrednost, teža ;
Objekt ( int vrednost, int utež )
: vrednost ( vrednost ) , utež ( utež )
{
}
} ;
bool cmp ( struct Objekt x, struct Objekt y )
{
dvojno A1 = ( dvojno ) x. vrednost / x. utež ;
dvojno A2 = ( dvojno ) in. vrednost / in. utež ;
vrnitev A1 > A2 ;
}
dvojno fractionalNahrbtnik ( struct Objekt arr [ ] ,
int IN, int velikost )
{
vrsta ( arr, arr + velikost, cmp ) ;
int curWeight = 0 ;
dvojno končna vrednost = 0,0 ;
za ( int jaz = 0 ; jaz < velikost ; jaz ++ ) {
če ( curWeight + prir [ jaz ] . utež <= IN ) {
curWeight + = prir [ jaz ] . utež ;
končna vrednost + = prir [ jaz ] . vrednost ;
}
drugače {
int ostanejo = IN - curWeight ;
končna vrednost + = prir [ jaz ] . vrednost
* ( ( dvojno ) ostanejo
/ prir [ jaz ] . utež ) ;
odmor ;
}
}
vrnitev končna vrednost ;
}
int v = 60 ;
Objekt arr [ ] = { { 100 , dvajset } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int velikost = sizeof ( prir ) / sizeof ( prir [ 0 ] ) ;
cout << 'Največji dobiček = '
<< fractionalNahrbtnik ( arr, v, vel ) ;
vrnitev 0 ;
}
V tej kodi je definirana struktura objekta, ki ima shranjene vrednosti teže in dobička. Bool cmp() se uporablja za primerjavo med dvema predmetoma na podlagi razmerja teže in vrednosti dveh predmetov. Matrika je urejena v padajočem vrstnem redu in vrednost se dodaja, dokler ne doseže največje vrednosti. Če je trenutna vrednost dopustna in v mejah, se doda, sicer pa se v vrečo doda njeno znižano razmerje. Velikost teže in vrednosti se vnese v glavno kodo, največji dobiček pa se natisne na izhodu.
Največji dobiček, ki je bil shranjen v prigrizku, je 580.
Zaključek
Problem delnega nahrbtnika v C++ se nanaša na prepoznavanje načina za polnjenje vrečke s predmeti dane teže in dobička na tak način, da vrečka vsebuje največjo vrednost, ne da bi presegla največjo omejitev. To je mogoče doseči s pohlepnim pristopom, katerega cilj je narediti idealne izbire na vsakem koraku, ki vodijo do idealne rešitve na koncu.