Det fraksjonerte ryggsekkproblemet i C++ refererer til å identifisere en måte å fylle en pose med gjenstander med en gitt vekt og fortjeneste på en slik måte at posen inneholder maksimumsverdien uten å overskride maksimumsgrensen.
Hvordan løse problemet med brøksekk i C++
Gitt et sett med varer, hver med gitt vekt og fortjeneste, bestemme hvert antall varer i en slik kombinasjon at totalvekten av varer er mindre enn maksgrensen for posen, men verdien må holdes så stor som mulig.
Algoritme for å implementere brøksekkproblemet
Funksjonen til Knapsack-algoritmen kan forstås gjennom følgende punkter:
- Ta to matriser med vekt og fortjeneste.
- Sett maksimal sekkverdi til W.
- Bestem tettheten ved å ta forholdet mellom begge parameterne.
- Sorter elementer i synkende rekkefølge etter tetthet.
- Legg sammen verdier til det er <=W.
Den grådige tilnærmingen til å løse problemet med brøksekk
Den grådige tilnærmingen tar sikte på å ta ideelle valg på hvert trinn, noe som fører til den ideelle løsningen på slutten. Det løser problemer trinn for trinn som fører til konklusjoner i stedet for å konkludere resultatene bare til slutt. Dette er en kildekode for å implementere en løsning på brøksekkproblemet i C++:
#include
ved hjelp av navneområde std ;
struktur Gjenstand {
int verdi, vekt ;
Gjenstand ( int verdi, int vekt )
: verdi ( verdi ) , vekt ( vekt )
{
}
} ;
bool cmp ( struktur Objekt x, struktur Objekt y )
{
dobbelt A1 = ( dobbelt ) x. verdi / x. vekt ;
dobbelt A2 = ( dobbelt ) og. verdi / og. vekt ;
komme tilbake A1 > A2 ;
}
dobbelt fraksjonellKnapsekk ( struktur Objekt arr [ ] ,
int I, int størrelse )
{
sortere ( arr, arr + størrelse, cmp ) ;
int curWeight = 0 ;
dobbelt sluttverdi = 0,0 ;
til ( int Jeg = 0 ; Jeg < størrelse ; Jeg ++ ) {
hvis ( curWeight + arr [ Jeg ] . vekt <= I ) {
curWeight + = arr [ Jeg ] . vekt ;
sluttverdi + = arr [ Jeg ] . verdi ;
}
ellers {
int forbli = I - curWeight ;
sluttverdi + = arr [ Jeg ] . verdi
* ( ( dobbelt ) forbli
/ arr [ Jeg ] . vekt ) ;
gå i stykker ;
}
}
komme tilbake sluttverdi ;
}
int i = 60 ;
Objekt arr [ ] = { { 100 , tjue } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int størrelse = størrelsen av ( arr ) / størrelsen av ( arr [ 0 ] ) ;
cout << 'Maksimal fortjeneste = '
<< fraksjonellKnapsekk ( arr, v, størrelse ) ;
komme tilbake 0 ;
}
I denne koden er det definert en objektstruktur som har vekt- og profittverdier lagret i seg. Bool cmp() brukes til å gjøre en sammenligning mellom to objekter på grunnlag av forholdet mellom vekt og verdi av to objekter. Matrisen er ordnet i synkende rekkefølge, og verdien fortsetter å legge til til den når maksimum. Hvis gjeldende verdi er tillatt og innenfor grensen, legges den til, ellers legges det reduserte forholdet til posen. Størrelsen på vekt og verdi legges inn i hovedkoden og maksimal fortjeneste skrives ut på utgangen.
Maksimal fortjeneste som ble lagret i snacken er 580.
Konklusjon
Det fraksjonerte ryggsekkproblemet i C++ refererer til å identifisere en måte å fylle en pose med gjenstander med en gitt vekt og fortjeneste på en slik måte at posen inneholder maksimumsverdien uten å overskride maksimumsgrensen. Dette kan oppnås ved den grådige tilnærmingen som tar sikte på å ta ideelle valg på hvert trinn, som fører til den ideelle løsningen på slutten.