Ako vyriešiť problém s frakčným batohom v C++

Vzhľadom na súbor položiek, každý s danou hmotnosťou a ziskom, určte každý počet položiek v takej kombinácii, aby celková hmotnosť položiek bola menšia ako maximálny limit vrecka, ale hodnota musí byť čo najväčšia.

Algoritmus na implementáciu problému zlomkového batohu

Fungovanie algoritmu batohu možno pochopiť pomocou nasledujúcich bodov:

Vezmite dve polia hmotnosti a zisku.
Nastavte maximálnu hodnotu vreca na W.
Určte hustotu pomerom oboch parametrov.
Zoraďte položky v zostupnom poradí podľa hustoty.
Sčítajte hodnoty, kým nebude <=W.

Nenásytný prístup k vyriešeniu problému s čiastočným batohom

Chamtivý prístup má za cieľ robiť ideálne rozhodnutia v každom kroku, čo na konci vedie k ideálnemu riešeniu. Rieši problémy krok za krokom, ktoré vedú k záverom, namiesto toho, aby končili iba výsledky. Toto je zdrojový kód na implementáciu riešenia problému s frakčným batohom v C++:

#include

použitím menný priestor std ;

štrukturovať Objekt {

int hodnota, hmotnosť ;

Objekt ( int hodnota, int hmotnosť )
: hodnotu ( hodnotu ) , hmotnosť ( hmotnosť )
{
}

} ;

bool cmp ( štrukturovať objekt x, štrukturovať Objekt y )

{

dvojitý A1 = ( dvojitý ) X. hodnotu / X. hmotnosť ;

dvojitý A2 = ( dvojitý ) a. hodnotu / a. hmotnosť ;

vrátiť A1 > A2 ;

}

dvojitý frakčný batoh ( štrukturovať Objekt arr [ ] ,
int IN, int veľkosť )
{

triediť ( arr, arr + veľkosť, cmp ) ;

int curWeight = 0 ;

dvojitý konečná hodnota = 0,0 ;

pre ( int i = 0 ; i < veľkosť ; i ++ ) {

ak ( curWeight + arr [ i ] . hmotnosť <= IN ) {
curWeight + = arr [ i ] . hmotnosť ;
konečná hodnota + = arr [ i ] . hodnotu ;
}

inak {
int zostať = IN - curWeight ;
konečná hodnota + = arr [ i ] . hodnotu
* ( ( dvojitý ) zostať
/ arr [ i ] . hmotnosť ) ;

prestávka ;
}
}

vrátiť konečná hodnota ;

}

int v = 60 ;

Objekt arr [ ] = { { 100 , dvadsať } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;

int veľkosť = veľkosť ( arr ) / veľkosť ( arr [ 0 ] ) ;

cout << 'Maximálny zisk ='

<< frakčný batoh ( arr, v, veľkosť ) ;

vrátiť 0 ;

}

V tomto kóde je definovaná štruktúra objektu, ktorá má v sebe uložené hodnoty váhy a zisku. Bool cmp() sa používa na porovnanie dvoch objektov na základe pomeru hmotnosti a hodnoty dvoch objektov. Pole je usporiadané v zostupnom poradí a hodnota sa neustále pridáva, kým nedosiahne maximum. Ak je aktuálna hodnota prípustná a v rámci limitu, pripočíta sa, v opačnom prípade sa do vrecka pripočíta jej znížený pomer. Veľkosť hmotnosti a hodnoty sa zadá do hlavného kódu a na výstupe sa vytlačí maximálny zisk.

Maximálny zisk, ktorý bol uložený v občerstvení, je 580.

Záver

Problém frakčného batohu v C++ sa týka identifikácie spôsobu, ako naplniť vrece položkami danej hmotnosti a zisku takým spôsobom, aby vrece obsahovalo maximálnu hodnotu bez prekročenia maximálneho limitu. To sa dá dosiahnuť chamtivým prístupom, ktorý má za cieľ robiť ideálne rozhodnutia v každom kroku, čo na konci vedie k ideálnemu riešeniu.

Ako vyriešiť problém s frakčným batohom v C++