A frakcionált hátizsák probléma a C++ nyelvben arra utal, hogy meghatározzuk azt a módot, amellyel egy zacskót meg lehet tölteni adott súlyú és nyereséges cikkekkel oly módon, hogy a táska a maximális értéket tartalmazza anélkül, hogy túllépné a maximális határt.
Hogyan lehet megoldani a frakcionált hátizsák problémát C++ nyelven
Adott egy tételsor, mindegyik adott súllyal és haszonnal, határozza meg az egyes cikkek darabszámát olyan kombinációban, hogy a tárgyak össztömege kisebb legyen, mint a táska maximális korlátja, de az értéket a lehető legnagyobb mértékben meg kell tartani.
Algoritmus a frakcionált hátizsák-probléma megvalósításához
A hátizsák-algoritmus működése a következő pontokon keresztül érthető meg:
- Vegyünk két súlyt és nyereséget.
- Állítsa a maximális zsákértéket W-re.
- Határozza meg a sűrűséget mindkét paraméter arányának figyelembevételével.
- Rendezze az elemeket a sűrűség szerint csökkenő sorrendbe.
- Add össze az értékeket, amíg <=W.
A töredékes hátizsák probléma megoldásának mohó megközelítése
A mohó megközelítés arra törekszik, hogy minden lépésben ideális választást hozzon, ami a végén az ideális megoldáshoz vezet. Lépésről lépésre oldja meg a problémákat, ami következtetésekhez vezet, ahelyett, hogy csak az eredményeket kötné le. Ez egy forráskód a tört hátizsák probléma megoldásának megvalósításához C++ nyelven:
#include
segítségével névtér std ;
struct Tárgy {
int érték, súly ;
Tárgy ( int érték, int súly )
: érték ( érték ) , súly ( súly )
{
}
} ;
bool cmp ( struct objektum x, struct y objektum )
{
kettős A1 = ( kettős ) x. érték / x. súly ;
kettős A2 = ( kettős ) és. érték / és. súly ;
Visszatérés A1 > A2 ;
}
kettős töredékes hátizsák ( struct Objektum arr [ ] ,
int BAN BEN, int méret )
{
fajta ( arr, arr + méret, cmp ) ;
int curWeight = 0 ;
kettős végső érték = 0.0 ;
számára ( int én = 0 ; én < méret ; én ++ ) {
ha ( curWeight + arr [ én ] . súly <= BAN BEN ) {
curWeight + = arr [ én ] . súly ;
végső érték + = arr [ én ] . érték ;
}
más {
int marad = BAN BEN - curWeight ;
végső érték + = arr [ én ] . érték
* ( ( kettős ) marad
/ arr [ én ] . súly ) ;
szünet ;
}
}
Visszatérés végső érték ;
}
int ban ben = 60 ;
Objektum arr [ ] = { { 100 , húsz } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int méret = mérete ( arr ) / mérete ( arr [ 0 ] ) ;
cout << 'Maximális nyereség ='
<< töredékes hátizsák ( arr, v, méret ) ;
Visszatérés 0 ;
}
Ebben a kódban egy objektumstruktúra van definiálva, amelyben súly- és profitértékek vannak tárolva. A bool cmp() két objektum összehasonlítására szolgál két objektum súlyának és értékének aránya alapján. A tömb csökkenő sorrendben van elrendezve, és az érték folyamatosan bővül, amíg el nem éri a maximumot. Ha az aktuális érték megengedett és a határon belül van, akkor hozzáadjuk, ellenkező esetben csökkentett aránya hozzáadódik a zsákhoz. A súly és az érték nagysága a fő kódba kerül beírásra, a kimenetre pedig a maximális profit kerül kinyomtatásra.
A snackben tárolt maximális nyereség 580.
Következtetés
A frakcionált hátizsák probléma a C++ nyelvben arra utal, hogy meghatározzuk azt a módot, amellyel egy zacskót meg lehet tölteni adott súlyú és nyereséges cikkekkel oly módon, hogy a táska a maximális értéket tartalmazza anélkül, hogy túllépné a maximális határt. Ezt a mohó megközelítéssel lehet elérni, amely minden lépésben ideális választást kíván meghozni, ami a végén az ideális megoldáshoz vezet.