Det fraktionelle rygsækproblem i C++ refererer til at identificere en måde at fylde en pose med genstande af en given vægt og fortjeneste på en sådan måde, at posen indeholder den maksimale værdi uden at overskride den maksimale grænse.
Sådan løses problemet med fraktioneret napsæk i C++
Givet et sæt af varer, hver med den givne vægt og fortjeneste, bestemme hvert antal varer i en sådan kombination, at den samlede vægt af varer er mindre end den maksimale grænse for posen, men værdien skal holdes så stor som muligt.
Algoritme til at implementere fraktionel rygsæk-problemet
Funktionen af Knapsack-algoritmen kan forstås gennem følgende punkter:
- Tag to arrays af vægt og overskud.
- Indstil den maksimale sækværdi til W.
- Bestem tætheden ved at tage forholdet mellem begge parametre.
- Sorter emner i faldende rækkefølge efter tæthed.
- Læg værdierne sammen, indtil det er <=W.
Den grådige tilgang til at løse problemet med fraktioneret rygsæk
Den grådige tilgang har til formål at træffe ideelle valg ved hvert trin, hvilket fører til den ideelle løsning til sidst. Det løser problemer trin for trin, der fører til konklusioner i stedet for kun at konkludere resultaterne i sidste ende. Dette er en kildekode til implementering af en løsning på det fraktionelle rygsækproblem i C++:
#include
ved brug af navneområde std ;
struktur Objekt {
int værdi, vægt ;
Objekt ( int værdi, int vægt )
: værdi ( værdi ) , vægt ( vægt )
{
}
} ;
bool cmp ( struktur Objekt x, struktur Objekt y )
{
dobbelt A1 = ( dobbelt ) x. værdi / x. vægt ;
dobbelt A2 = ( dobbelt ) og. værdi / og. vægt ;
Vend tilbage A1 > A2 ;
}
dobbelt fraktioneretKnapsæk ( struktur Objekt arr [ ] ,
int I, int størrelse )
{
sortere ( arr, arr + størrelse, cmp ) ;
int curWeight = 0 ;
dobbelt slutværdi = 0,0 ;
til ( int jeg = 0 ; jeg < størrelse ; jeg ++ ) {
hvis ( curWeight + arr [ jeg ] . vægt <= I ) {
curWeight + = arr [ jeg ] . vægt ;
slutværdi + = arr [ jeg ] . værdi ;
}
andet {
int forblive = I - curWeight ;
slutværdi + = arr [ jeg ] . værdi
* ( ( dobbelt ) forblive
/ arr [ jeg ] . vægt ) ;
pause ;
}
}
Vend tilbage slutværdi ;
}
int i = 60 ;
Objekt arr [ ] = { { 100 , tyve } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int størrelse = størrelse på ( arr ) / størrelse på ( arr [ 0 ] ) ;
cout << 'Maksimal fortjeneste = '
<< fraktioneretKnapsæk ( arr, v, størrelse ) ;
Vend tilbage 0 ;
}
I denne kode er en objektstruktur defineret, som har vægt- og profitværdier gemt i sig. Bool cmp() bruges til at foretage en sammenligning mellem to objekter på basis af forholdet mellem vægt og værdi af to objekter. Arrayet er arrangeret i faldende rækkefølge, og værdien bliver ved med at tilføje, indtil den når maksimum. Hvis den aktuelle værdi er tilladt og inden for grænsen, tilføjes den, ellers tilføjes dens reducerede forhold til posen. Størrelsen af vægt og værdi indtastes i hovedkoden, og den maksimale fortjeneste udskrives på outputtet.
Den maksimale fortjeneste, der blev opbevaret i snacken, er 580.
Konklusion
Det fraktionelle rygsækproblem i C++ refererer til at identificere en måde at fylde en pose med genstande af en given vægt og fortjeneste på en sådan måde, at posen indeholder den maksimale værdi uden at overskride den maksimale grænse. Dette kan opnås ved den grådige tilgang, der sigter mod at træffe ideelle valg ved hvert trin, hvilket fører til den ideelle løsning til sidst.