El problema de la motxilla fraccionada en C++ es refereix a identificar una manera d'omplir una bossa amb articles d'un pes i un benefici determinats de tal manera que la bossa contingui el valor màxim sense superar el límit màxim.
Com resoldre el problema de la motxilla fraccionada en C++
Donat un conjunt d'articles, cadascun amb el pes i el benefici donats, determineu cada nombre d'articles en una combinació tal que el pes total dels articles sigui inferior al límit màxim de la bossa, però el valor s'ha de mantenir el més gran possible.
Algorisme per implementar el problema de la motxilla fraccional
El funcionament de l'algorisme Knapsack es pot entendre a través dels punts següents:
- Preneu dues matrius de pes i benefici.
- Estableix el valor màxim del sac a W.
- Determineu la densitat prenent la relació d'ambdós paràmetres.
- Ordena els elements en ordre decreixent de densitat.
- Sumeu valors fins que sigui <=W.
L'enfocament cobdiciós per resoldre el problema de la motxilla fraccionada
L'enfocament cobdiciós pretén prendre decisions ideals a cada pas, que condueixin a la solució ideal al final. Soluciona problemes pas a pas que condueixen a conclusions en lloc de concloure els resultats només al final. Aquest és un codi font per implementar una solució al problema de la motxilla fraccionada en C++:
#inclou
utilitzant espai de noms std ;
estructura Objecte {
int valor, pes ;
Objecte ( int valor, int pes )
: valor ( valor ) , pes ( pes )
{
}
} ;
bool cmp ( estructura Objecte x, estructura Objecte y )
{
doble A1 = ( doble ) x. valor / x. pes ;
doble A2 = ( doble ) i. valor / i. pes ;
tornar A1 > A2 ;
}
doble motxilla fraccionada ( estructura Objecte arr [ ] ,
int EN, int mida )
{
ordenar ( arr, arr + mida, cmp ) ;
int curWeight = 0 ;
doble valor final = 0.0 ;
per ( int i = 0 ; i < mida ; i ++ ) {
si ( curWeight + arr [ i ] . pes <= EN ) {
curWeight + = arr [ i ] . pes ;
valor final + = arr [ i ] . valor ;
}
altra cosa {
int romandre = EN - curWeight ;
valor final + = arr [ i ] . valor
* ( ( doble ) romandre
/ arr [ i ] . pes ) ;
trencar ;
}
}
tornar valor final ;
}
int en = 60 ;
Objecte arr [ ] = { { 100 , 20 } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int mida = mida de ( arr ) / mida de ( arr [ 0 ] ) ;
cout << 'Guanyi màxim ='
<< motxilla fraccionada ( arr, v, mida ) ;
tornar 0 ;
}
En aquest codi, es defineix una estructura d'objectes que té valors de pes i beneficis emmagatzemats. El bool cmp() s'utilitza per fer una comparació entre dos objectes sobre la base de la relació de pes i valor de dos objectes. La matriu s'ordena en ordre descendent i el valor continua sumant fins que arriba al màxim. Si el valor actual és admissible i dins del límit, s'afegeix, en cas contrari la seva relació reduïda s'afegeix a la bossa. La magnitud del pes i el valor s'introdueix al codi principal i el benefici màxim s'imprimeix a la sortida.
El benefici màxim que es va emmagatzemar al berenar és de 580.
Conclusió
El problema de la motxilla fraccionada en C++ es refereix a identificar una manera d'omplir una bossa amb articles d'un pes i un benefici determinats de tal manera que la bossa contingui el valor màxim sense superar el límit màxim. Això es pot aconseguir mitjançant l'enfocament cobdiciós que pretén prendre decisions ideals a cada pas, que condueixin a la solució ideal al final.