Daļējas mugursomas problēma valodā C++ attiecas uz to, kā noteikt veidu, kā piepildīt maisu ar noteikta svara un peļņas priekšmetiem tā, lai maisā būtu maksimālā vērtība, nepārsniedzot maksimālo robežu.
Kā atrisināt frakcionētu mugursomas problēmu programmā C++
Dotā vienību komplektā, katrai ar doto svaru un peļņu, katru priekšmetu skaitu nosaki tādā kombinācijā, lai kopējais priekšmetu svars būtu mazāks par somas maksimālo limitu, bet vērtība jāsaglabā pēc iespējas lielāka.
Algoritms frakcionētas mugursomas problēmas īstenošanai
Knapsack algoritma darbību var saprast, izmantojot šādus punktus:
- Paņemiet divus svara un peļņas masīvus.
- Iestatiet maksimālo maisa vērtību uz W.
- Nosakiet blīvumu, izmantojot abu parametru attiecību.
- Kārtojiet vienumus dilstošā blīvuma secībā.
- Saskaitiet vērtības, līdz tas ir <=W.
Mantkārīgā pieeja frakcionētas mugursomas problēmas risināšanai
Mantkārīgās pieejas mērķis ir katrā solī izdarīt ideālu izvēli, kas beigās noved pie ideālā risinājuma. Tas soli pa solim atrisina problēmas, izdarot secinājumus, nevis tikai beigās secina rezultātus. Šis ir avota kods daļējas mugursomas problēmas risinājuma ieviešanai programmā C++:
#include
izmantojot nosaukumvieta std ;
struktūra Objekts {
starpt vērtība, svars ;
Objekts ( starpt vērtība, starpt svars )
: vērtību ( vērtību ) , svars ( svars )
{
}
} ;
bool cmp ( struktūra objekts x, struktūra Objekts y )
{
dubultā A1 = ( dubultā ) x. vērtību / x. svars ;
dubultā A2 = ( dubultā ) un. vērtību / un. svars ;
atgriezties A1 > A2 ;
}
dubultā daļēja Mugursoma ( struktūra Objekta arr [ ] ,
starpt IN, starpt Izmērs )
{
kārtot ( arr, arr + izmērs, cmp ) ;
starpt curWeight = 0 ;
dubultā galīgā vērtība = 0,0 ;
priekš ( starpt i = 0 ; i < Izmērs ; i ++ ) {
ja ( curWeight + arr [ i ] . svars <= IN ) {
curWeight + = arr [ i ] . svars ;
galīgā vērtība + = arr [ i ] . vērtību ;
}
cits {
starpt paliek = IN - curWeight ;
galīgā vērtība + = arr [ i ] . vērtību
* ( ( dubultā ) paliek
/ arr [ i ] . svars ) ;
pārtraukums ;
}
}
atgriezties galīgā vērtība ;
}
starpt iekšā = 60 ;
Objekta arr [ ] = { { 100 , divdesmit } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
starpt Izmērs = izmērs ( arr ) / izmērs ( arr [ 0 ] ) ;
cout << 'Maksimālā peļņa ='
<< daļēja Mugursoma ( arr, v, izmērs ) ;
atgriezties 0 ;
}
Šajā kodā ir definēta objekta struktūra, kurā ir saglabātas svara un peļņas vērtības. Bool cmp () tiek izmantots, lai salīdzinātu divus objektus, pamatojoties uz divu objektu svara un vērtības attiecību. Masīvs ir sakārtots dilstošā secībā, un vērtība tiek pievienota, līdz tā sasniedz maksimumu. Ja pašreizējā vērtība ir pieļaujama un robežās, tā tiek pievienota, pretējā gadījumā tās samazinātā attiecība tiek pievienota maisam. Svara un vērtības lielums tiek ievadīts galvenajā kodā, un maksimālā peļņa tiek uzdrukāta uz izvades.
Maksimālā peļņa, kas tika uzkrāta uzkodā, ir 580.
Secinājums
Daļējas mugursomas problēma valodā C++ attiecas uz to, kā noteikt veidu, kā piepildīt maisu ar noteikta svara un peļņas priekšmetiem tā, lai maisā būtu maksimālā vērtība, nepārsniedzot maksimālo robežu. To var panākt ar mantkārīgo pieeju, kuras mērķis ir katrā solī izdarīt ideālu izvēli, kas beigās noved pie ideālā risinājuma.