Dalinės kuprinės problema C++ kalboje reiškia būdą, kaip užpildyti maišą tam tikro svorio ir pelno turinčiais daiktais taip, kad maiše būtų didžiausia vertė, neviršijant didžiausios ribos.
Kaip išspręsti trupmeninės kuprinės problemą C++
Atsižvelgiant į daiktų rinkinį, kurių kiekvienas turi nurodytą svorį ir pelną, kiekvieną prekių skaičių nustatykite tokia kombinacija, kad bendras daiktų svoris būtų mažesnis už maksimalią maišelio ribą, tačiau vertė turi būti kuo didesnė.
Dalinės kuprinės problemos įgyvendinimo algoritmas
„Knapsack“ algoritmo veikimą galima suprasti per šiuos dalykus:
- Paimkite du svorio ir pelno matricas.
- Nustatykite didžiausią maišo vertę į W.
- Nustatykite tankį, atsižvelgdami į abiejų parametrų santykį.
- Rūšiuokite elementus mažėjančia tankio tvarka.
- Sudėkite reikšmes, kol ji bus <=W.
Godus būdas išspręsti trupmeninės kuprinės problemą
Godus požiūris siekia kiekviename žingsnyje padaryti idealų pasirinkimą, o pabaigoje - idealų sprendimą. Jis žingsnis po žingsnio išsprendžia problemas ir daro išvadas, o ne tik baigia rezultatus. Tai šaltinio kodas, skirtas įgyvendinti trupmeninės kuprinės problemos sprendimą C++:
#include
naudojant vardų erdvė std ;
struktūra Objektas {
tarpt vertė, svoris ;
Objektas ( tarpt vertė, tarpt svorio )
: vertė ( vertė ) , svoris ( svorio )
{
}
} ;
bool cmp ( struktūra Objektas x, struktūra Objektas y )
{
dvigubai A1 = ( dvigubai ) x. vertė / x. svorio ;
dvigubai A2 = ( dvigubai ) ir. vertė / ir. svorio ;
grąžinti A1 > A2 ;
}
dvigubai trupmeninė Kuprinė ( struktūra Objektas arr [ ] ,
tarpt IN, tarpt dydis )
{
rūšiuoti ( arr, arr + dydis, cmp ) ;
tarpt curWeight = 0 ;
dvigubai galutinė vertė = 0,0 ;
dėl ( tarpt i = 0 ; i < dydis ; i ++ ) {
jeigu ( curWeight + arr [ i ] . svorio <= IN ) {
curWeight + = arr [ i ] . svorio ;
galutinė vertė + = arr [ i ] . vertė ;
}
Kitas {
tarpt likti = IN - curWeight ;
galutinė vertė + = arr [ i ] . vertė
* ( ( dvigubai ) likti
/ arr [ i ] . svorio ) ;
pertrauka ;
}
}
grąžinti galutinė vertė ;
}
tarpt in = 60 ;
Objektas arr [ ] = { { 100 , dvidešimt } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
tarpt dydis = dydis ( arr ) / dydis ( arr [ 0 ] ) ;
cout << 'Maksimalus pelnas ='
<< trupmeninė Kuprinė ( arr, v, dydis ) ;
grąžinti 0 ;
}
Šiame kode apibrėžiama objekto struktūra, kurioje saugomos svorio ir pelno reikšmės. Bool cmp() naudojamas dviejų objektų palyginimui pagal dviejų objektų svorio ir vertės santykį. Masyvas yra išdėstytas mažėjančia tvarka, o vertė nuolat pridedama, kol pasiekia maksimumą. Jei dabartinė vertė yra leistina ir neviršija ribos, ji pridedama, kitaip sumažintas santykis pridedamas prie maišo. Svorio dydis ir vertė įvedami į pagrindinį kodą, o maksimalus pelnas atspausdinamas ant išvesties.
Didžiausias pelnas, kuris buvo sukauptas užkandyje, yra 580.
Išvada
Dalinės kuprinės problema C++ kalboje reiškia būdą, kaip užpildyti maišą tam tikro svorio ir pelno turinčiais daiktais taip, kad maiše būtų didžiausia vertė, neviršijant didžiausios ribos. Tai galima pasiekti taikant godų požiūrį, kurio tikslas – kiekviename žingsnyje padaryti idealų pasirinkimą, o pabaigoje – idealų sprendimą.