C++ fraktsionaalse seljakoti probleem viitab viiside tuvastamisele, kuidas täita kott teatud kaalu ja tuluga esemetega nii, et kott sisaldaks maksimaalset väärtust, ületamata seejuures maksimaalset piiri.
Kuidas lahendada fraktsionaalse seljakoti probleemi C++ keeles
Arvestades esemete komplekti, millest igaühel on antud kaal ja kasum, määrake iga esemete arv sellises kombinatsioonis, et esemete kogukaal on väiksem kui koti maksimumlimiit, kuid väärtust tuleb hoida võimalikult suur.
Algoritm fraktsionaalse seljakoti probleemi rakendamiseks
Knapsacki algoritmi toimimist saab mõista järgmiste punktide kaudu:
- Võtke kaks massi ja kasumi massiivi.
- Seadke koti maksimaalseks väärtuseks W.
- Määrake tihedus, võttes mõlema parameetri suhte.
- Sorteeri üksused tiheduse kahanevas järjekorras.
- Lisage väärtusi, kuni see on <=W.
Ahne lähenemisviis fraktsionaalse seljakoti probleemi lahendamiseks
Ahne lähenemine püüab igal sammul teha ideaalseid valikuid, mis viivad lõpuks ideaalse lahenduseni. See lahendab probleemid samm-sammult, mis viib järeldusteni, selle asemel et teha järeldusi ainult tulemuste kohta. See on lähtekood fraktsionaalse seljakoti probleemi lahendamiseks C++ keeles:
#include
kasutades nimeruum std ;
struktuur Objekt {
int väärtus, kaal ;
Objekt ( int väärtus, int kaal )
: väärtus ( väärtus ) , kaal ( kaal )
{
}
} ;
bool cmp ( struktuur objekt x, struktuur Objekt y )
{
kahekordne A1 = ( kahekordne ) x. väärtus / x. kaal ;
kahekordne A2 = ( kahekordne ) ja. väärtus / ja. kaal ;
tagasi A1 > A2 ;
}
kahekordne murdosaKott ( struktuur Objekti arr [ ] ,
int IN, int suurus )
{
sorteerida ( arr, arr + suurus, cmp ) ;
int curWeight = 0 ;
kahekordne lõppväärtus = 0,0 ;
jaoks ( int i = 0 ; i < suurus ; i ++ ) {
kui ( curWeight + arr [ i ] . kaal <= IN ) {
curWeight + = arr [ i ] . kaal ;
lõppväärtus + = arr [ i ] . väärtus ;
}
muidu {
int jääma = IN - curWeight ;
lõppväärtus + = arr [ i ] . väärtus
* ( ( kahekordne ) jääma
/ arr [ i ] . kaal ) ;
murda ;
}
}
tagasi lõppväärtus ;
}
int sisse = 60 ;
Objekti arr [ ] = { { 100 , kakskümmend } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int suurus = suurus ( arr ) / suurus ( arr [ 0 ] ) ;
cout << 'Maksimaalne kasum ='
<< murdosaKott ( arr, v, suurus ) ;
tagasi 0 ;
}
Selles koodis on määratletud objekti struktuur, millesse on salvestatud kaalu ja kasumi väärtused. Bool cmp() kasutatakse kahe objekti võrdlemiseks kahe objekti kaalu ja väärtuse suhte alusel. Massiiv on järjestatud kahanevas järjekorras ja väärtust lisatakse, kuni see saavutab maksimumi. Kui praegune väärtus on lubatud ja piires, lisatakse see, vastasel juhul lisatakse kotile selle vähendatud suhe. Kaalu ja väärtuse suurus sisestatakse põhikoodi ning maksimaalne kasum trükitakse väljundile.
Suupistesse salvestatud maksimaalne kasum on 580.
Järeldus
C++ fraktsionaalse seljakoti probleem viitab viiside tuvastamisele, kuidas täita kott teatud kaalu ja tuluga esemetega nii, et kott sisaldaks maksimaalset väärtust, ületamata seejuures maksimaalset piiri. Seda saab saavutada ahne lähenemisviisiga, mille eesmärk on teha igal sammul ideaalseid valikuid, mis viib lõpuks ideaalse lahenduseni.