Problemet med fraktionerad ryggsäck i C++ hänvisar till att identifiera ett sätt att fylla en påse med föremål med en given vikt och vinst på ett sådant sätt att påsen innehåller maxvärdet utan att överskrida maxgränsen.
Hur man löser Fractional Knapsack-problemet i C++
Givet en uppsättning artiklar, var och en med given vikt och vinst, bestäm varje antal artiklar i en sådan kombination att den totala vikten av artiklar är mindre än maxgränsen för påsen, men värdet måste hållas så stort som möjligt.
Algoritm för att implementera Fractional Knapsack-problemet
Funktionen av Knapsack-algoritmen kan förstås genom följande punkter:
- Ta två matriser av vikt och vinst.
- Ställ in det maximala säckvärdet till W.
- Bestäm densiteten genom att ta förhållandet mellan båda parametrarna.
- Sortera objekt i minskande täthetsordning.
- Lägg ihop värden tills det är <=W.
Det giriga tillvägagångssättet för att lösa problemet med fraktionerad ryggsäck
Det giriga tillvägagångssättet syftar till att göra idealiska val vid varje steg, vilket leder till den ideala lösningen i slutet. Det löser problem steg för steg som leder till slutsatser istället för att bara dra slutsatserna i slutändan. Det här är en källkod för att implementera en lösning på problemet med fraktionerad ryggsäck i C++:
#include
använder sig av namnutrymme std ;
struktur Objekt {
int värde, vikt ;
Objekt ( int värde, int vikt )
: värde ( värde ) , vikt ( vikt )
{
}
} ;
bool cmp ( struktur Objekt x, struktur Objekt y )
{
dubbel A1 = ( dubbel ) x. värde / x. vikt ;
dubbel A2 = ( dubbel ) och. värde / och. vikt ;
lämna tillbaka A1 > A2 ;
}
dubbel fraktionellKnappsäck ( struktur Objekt arr [ ] ,
int I, int storlek )
{
sortera ( arr, arr + storlek, cmp ) ;
int curWeight = 0 ;
dubbel slutvärde = 0,0 ;
för ( int i = 0 ; i < storlek ; i ++ ) {
om ( curWeight + arr [ i ] . vikt <= I ) {
curWeight + = arr [ i ] . vikt ;
slutvärde + = arr [ i ] . värde ;
}
annan {
int förbli = I - curWeight ;
slutvärde + = arr [ i ] . värde
* ( ( dubbel ) förbli
/ arr [ i ] . vikt ) ;
ha sönder ;
}
}
lämna tillbaka slutvärde ;
}
int i = 60 ;
Objekt arr [ ] = { { 100 , tjugo } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int storlek = storlek av ( arr ) / storlek av ( arr [ 0 ] ) ;
cout << 'Maximal vinst = '
<< fraktionellKnappsäck ( arr, v, storlek ) ;
lämna tillbaka 0 ;
}
I denna kod definieras en objektstruktur som har vikt- och vinstvärden lagrade i sig. Bool cmp() används för att göra en jämförelse mellan två objekt på basis av förhållandet mellan vikt och värde för två objekt. Arrayen är ordnad i fallande ordning och värdet fortsätter att läggas till tills det når maximalt. Om det aktuella värdet är tillåtet och inom gränsen läggs det till, annars läggs dess reducerade förhållande till påsen. Storleken på vikt och värde skrivs in i huvudkoden och den maximala vinsten skrivs ut på utgången.
Den maximala vinsten som lagrades i mellanmålet är 580.
Slutsats
Problemet med fraktionerad ryggsäck i C++ hänvisar till att identifiera ett sätt att fylla en påse med föremål med en given vikt och vinst på ett sådant sätt att påsen innehåller maxvärdet utan att överskrida maxgränsen. Detta kan uppnås genom det giriga tillvägagångssättet som syftar till att göra perfekta val vid varje steg, vilket leder till den ideala lösningen i slutet.