Het fractionele knapzakprobleem in C++ verwijst naar het identificeren van een manier om een tas te vullen met items van een bepaald gewicht en winst, op een zodanige manier dat de tas de maximale waarde bevat zonder de maximale limiet te overschrijden.
Hoe het fractionele knapzakprobleem in C++ op te lossen
Gegeven een set items, elk met het opgegeven gewicht en de winst, bepaal je elk aantal items in een zodanige combinatie dat het totale gewicht van de items kleiner is dan de maximale limiet van de tas, maar de waarde moet zo groot mogelijk worden gehouden.
Algoritme om het fractionele knapzakprobleem te implementeren
De werking van het Knapsack-algoritme kan worden begrepen aan de hand van de volgende punten:
- Neem twee reeksen gewicht en winst.
- Stel de maximale zakwaarde in op W.
- Bepaal de dichtheid door de verhouding van beide parameters te nemen.
- Sorteer items in afnemende volgorde van dichtheid.
- Tel waarden op tot <=W.
De hebzuchtige aanpak om het fractionele knapzakprobleem op te lossen
De hebzuchtige benadering is erop gericht om bij elke stap de ideale keuzes te maken, die uiteindelijk tot de ideale oplossing leiden. Het lost problemen stap voor stap op en leidt tot conclusies in plaats van alleen maar tot de conclusie te komen. Dit is een broncode voor het implementeren van een oplossing voor het fractionele knapzakprobleem in C++:
#include
gebruik makend van naamruimte soa ;
structureren Voorwerp {
int waarde, gewicht ;
Voorwerp ( int waarde, int gewicht )
: waarde ( waarde ) , gewicht ( gewicht )
{
}
} ;
bool cmp ( structureren Voorwerp x, structureren Object y )
{
dubbele A1 = ( dubbele ) X. waarde / X. gewicht ;
dubbele A2 = ( dubbele ) En. waarde / En. gewicht ;
opbrengst A1 > A2 ;
}
dubbele fractioneleKnapzak ( structureren Object arr [ ] ,
int IN, int maat )
{
soort ( arr, arr + maat, cm ) ;
int curGewicht = 0 ;
dubbele eindwaarde = 0,0 ;
voor ( int i = 0 ; i < maat ; i ++ ) {
als ( curGewicht + arr [ i ] . gewicht <= IN ) {
curGewicht + = arr [ i ] . gewicht ;
eindwaarde + = arr [ i ] . waarde ;
}
anders {
int blijven = IN - curGewicht ;
eindwaarde + = arr [ i ] . waarde
* ( ( dubbele ) blijven
/ arr [ i ] . gewicht ) ;
pauze ;
}
}
opbrengst eindwaarde ;
}
int in = 60 ;
Object arr [ ] = { { 100 , twintig } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int maat = De grootte van ( arr ) / De grootte van ( arr [ 0 ] ) ;
uit << 'Maximale winst = '
<< fractioneleKnapzak ( arr, v, maat ) ;
opbrengst 0 ;
}
In deze code wordt een objectstructuur gedefinieerd waarin gewichts- en winstwaarden zijn opgeslagen. De bool cmp() wordt gebruikt om een vergelijking te maken tussen twee objecten op basis van de verhouding tussen gewicht en waarde van twee objecten. De array is in aflopende volgorde gerangschikt en de waarde blijft toenemen totdat deze het maximum bereikt. Als de huidige waarde is toegestaan en binnen de limiet ligt, wordt deze toegevoegd, anders wordt de gereduceerde verhouding aan de zak toegevoegd. De omvang van het gewicht en de waarde worden in de hoofdcode ingevoerd en de maximale winst wordt op de uitvoer afgedrukt.
De maximale winst die in de snack is opgeslagen, is 580.
Conclusie
Het fractionele knapzakprobleem in C++ verwijst naar het identificeren van een manier om een tas te vullen met items van een bepaald gewicht en winst, op een zodanige manier dat de tas de maximale waarde bevat zonder de maximale limiet te overschrijden. Dit kan worden bereikt door de hebzuchtige aanpak die erop gericht is bij elke stap de ideale keuzes te maken, die uiteindelijk tot de ideale oplossing leiden.