Šeit mugursoma ir kā konteiners vai soma. Pieņemsim, ka esam norādījuši dažus priekšmetus, kuriem ir kāds svars vai peļņa. Mums ir jāieliek daži priekšmeti mugursomā tā, lai kopējā vērtība radītu maksimālu peļņu.

Piemēram, konteinera svars ir 20 kg. Mums ir jāatlasa preces tā, lai preču svara summa būtu mazāka vai vienāda ar konteinera svaru un peļņa būtu maksimāla.

Ir divu veidu mugursomas problēmas:

• 0/1 mugursomas problēma
• Frakcionētas mugursomas problēma

Mēs apspriedīsim abas problēmas pa vienam. Pirmkārt, mēs uzzināsim par 0/1 mugursomas problēmu.

Kāda ir 0/1 mugursomas problēma?

0/1 mugursomas problēma nozīmē, ka mugursomā preces ir vai nu pilnībā, vai arī tās nav iepildītas. Piemēram, mums ir divas preces, kuru svars ir attiecīgi 2 kg un 3 kg. Ja mēs izvēlamies 2 kg preci, mēs nevaram izvēlēties 1 kg preci no 2 kg preces (prece nav dalāma); mums pilnībā jāizvēlas 2 kg prece. Šī ir 0/1 mugursomas problēma, kurā vai nu mēs izvēlamies preci pilnībā, vai arī izvēlamies to. 0/1 mugursomas problēma tiek atrisināta ar dinamisko programmēšanu.

Kāda ir daļējas mugursomas problēma?

Daļējas mugursomas problēma nozīmē, ka mēs varam sadalīt vienumu. Piemēram, mums ir 3 kg prece, tad mēs varam izvēlēties 2 kg preci un atstāt 1 kg smagu preci. Daļējas mugursomas problēma tiek atrisināta, izmantojot Mantkārīgo pieeju.

0/1 mugursomas problēmas piemērs.

Apsveriet problēmu ar svaru un peļņu:

Svari: {3, 4, 6, 5}

Peļņa: {2, 3, 1, 4}

Mugursomas svars ir 8 kg

Vienību skaits ir 4

Iepriekš minēto problēmu var atrisināt, izmantojot šādu metodi:

x_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

rhel vs centos

= {0, 1, 0, 1}

Iepriekš minētās ir iespējamās kombinācijas. 1 norāda, ka prece ir pilnībā paņemta, un 0 nozīmē, ka prece nav paņemta. Tā kā ir 4 preces, iespējamās kombinācijas būs:

2⁴= 16; Tātad. Ir 16 iespējamās kombinācijas, kuras var izveidot, izmantojot iepriekš minēto problēmu. Kad visas kombinācijas ir izveidotas, mums ir jāizvēlas kombinācija, kas nodrošina maksimālo peļņu.

Vēl viena pieeja problēmas risināšanai ir dinamiskās programmēšanas pieeja. Dinamiskās programmēšanas pieejā sarežģītā problēma tiek sadalīta apakšproblēmās, tad tiek atrasts apakšproblēmas risinājums un apakšproblēmas risinājums tiks izmantots sarežģītas problēmas risinājuma atrašanai.

Kā šo problēmu var atrisināt, izmantojot dinamiskās programmēšanas pieeju?

Pirmkārt,

mēs izveidojam matricu, kā parādīts zemāk:

Iepriekš minētajā matricā kolonnas attēlo svaru, t.i., 8. Rindas atspoguļo vienību peļņu un svarus. Šeit mēs neesam ņēmuši tieši svaru 8, problēma ir sadalīta apakšproblēmās, t.i., 0, 1, 2, 3, 4, 5, 6, 7, 8. Apakšuzdevumu risinājums tiktu saglabāts šūnas un atbilde uz problēmu tiks saglabāta pēdējā šūnā. Pirmkārt, mēs rakstām svarus augošā secībā un peļņu atbilstoši to svariem, kā parādīts tālāk:

In_i= {3, 4, 5, 6}

lpp_i= {2, 3, 4, 1}

Pirmā rinda un pirmā kolonna būtu 0, jo w=0 nav neviena vienuma

Kad i=1, W=1

In₁= 3; Tā kā mums komplektā ir tikai viena prece ar svaru 3, bet mugursomas ietilpība ir 1. Mēs nevaram aizpildīt 3 kg priekšmetu mugursomā ar ietilpību 1 kg, tāpēc pievienojiet 0 pie M[1][1], kā parādīts zemāk. :

Kad i = 1, W = 2

In₁= 3; Tā kā mums komplektā ir tikai viena prece ar svaru 3, bet mugursomas ietilpība ir 2. Mēs nevaram aizpildīt 3 kg priekšmetu mugursomā ar ietilpību 2 kg, tāpēc pievienojiet 0 pie M[1][2], kā parādīts zemāk. :

Kad i=1, W=3

In₁= 3; Tā kā mums komplektā ir tikai viena prece, kuras svars ir vienāds ar 3, un arī mugursomas svars ir 3; tāpēc mēs varam piepildīt mugursomu ar priekšmetu, kura svars ir vienāds ar 3. Mēs uzliekam peļņu, kas atbilst svaram 3, t.i., 2 pie M[1][3], kā parādīts zemāk:

Ja i = 1, W = 4

_W1= 3; Tā kā mums komplektā ir tikai viena prece, kuras svars ir vienāds ar 3, un mugursomas svars ir 4; tāpēc mēs varam piepildīt mugursomu ar priekšmetu, kura svars ir vienāds ar 3. Mēs ieliekam peļņu, kas atbilst svaram 3, t.i., 2 pie M[1][4], kā parādīts zemāk:

Ja i = 1, W = 5

_W1= 3; Tā kā mums komplektā ir tikai viena prece, kuras svars ir vienāds ar 3, un mugursomas svars ir 5; tāpēc mēs varam piepildīt mugursomu ar priekšmetu, kura svars ir vienāds ar 3. Mēs uzliekam peļņu, kas atbilst svaram 3, t.i., 2 pie M[1][5], kā parādīts zemāk:

Kad i = 1, W = 6

_W1= 3; Tā kā mums komplektā ir tikai viena prece, kuras svars ir vienāds ar 3, un mugursomas svars ir 6; tāpēc mēs varam piepildīt mugursomu ar priekšmetu, kura svars ir vienāds ar 3. Mēs uzliekam peļņu, kas atbilst svaram 3, t.i., 2 pie M[1][6], kā parādīts zemāk:

Ja i = 1, W = 7

_W1= 3; Tā kā mums komplektā ir tikai viena prece, kuras svars ir vienāds ar 3, un mugursomas svars ir 7; tāpēc mēs varam piepildīt mugursomu ar priekšmetu, kura svars ir vienāds ar 3. Mēs ieliekam peļņu, kas atbilst svaram 3, t.i., 2 pie M[1][7], kā parādīts zemāk:

Kad i = 1, W = 8

_W1= 3; Tā kā mums komplektā ir tikai viena prece, kuras svars ir vienāds ar 3, un mugursomas svars ir 8; tāpēc mēs varam piepildīt mugursomu ar priekšmetu, kura svars ir vienāds ar 3. Mēs uzliekam peļņu, kas atbilst svaram 3, t.i., 2 pie M[1][8], kā parādīts zemāk:

Tagad “i” vērtība tiek palielināta un kļūst par 2.

Ja i = 2, W = 1

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā komplektā ir tikai viena prece, kuras svars ir vienāds ar 4, un mugursomas svars ir 1. Mēs nevaram ievietot 4. svara priekšmetu mugursomā, tāpēc pie M[2][1 mēs pievienojam 0. ] parādīts šādi:

Kad i = 2, W = 2

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā komplektā ir tikai viena prece, kuras svars ir vienāds ar 4, un mugursomas svars ir 2. Mēs nevaram ievietot 4. svara priekšmetu mugursomā, tāpēc pie M[2][2 mēs pievienojam 0. ] parādīts šādi:

Kad i = 2, W = 3

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā mums komplektā ir divi priekšmeti, kuru svars ir 3 un 4, un mugursomas svars ir 3. Mēs varam ievietot 3. svara priekšmetu mugursomā, tāpēc mēs pievienojam 2 pie M[2][3] parādīts zemāk:

Kad i = 2, W = 4

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā mums komplektā ir divas preces ar svaru 3 un 4, un mugursomas svars ir 4. Mēs varam ievietot 4. svara priekšmetu mugursomā, jo peļņa, kas atbilst svaram 4, ir lielāka nekā precei ar svaru. 3, tāpēc mēs pievienojam 3 pie M[2][4], kā parādīts zemāk:

Ja i = 2, W = 5

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā mums komplektā ir divi priekšmeti ar atsvariem 3 un 4, un mugursomas svars ir 5. Mēs varam ievietot 4. svara priekšmetu mugursomā un svaram atbilstošā peļņa ir 3, tāpēc mēs pievienojam 3 M[2][5] parādīts šādi:

Ja i = 2, W = 6

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā mums komplektā ir divas preces ar atsvariem 3 un 4, un mugursomas svars ir 6. Mēs varam ievietot 4. svara priekšmetu mugursomā un svaram atbilstošā peļņa ir 3, tāpēc mēs pievienojam 3 M[2][6] parādīts šādi:

Ja i = 2, W = 7

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā mums komplektā ir divas preces ar atsvariem 3 un 4, un mugursomas svars ir 7. Mēs varam ielikt mugursomā 4. un 3. svara priekšmetu un atsvariem atbilstošā peļņa ir 2 un 3; tāpēc kopējā peļņa ir 5, tāpēc mēs pievienojam 5 pie M[2][7], kā parādīts zemāk:

Kad i = 2, W = 8

Svars, kas atbilst vērtībai 2, ir 4, t.i., w₂= 4. Tā kā mums komplektā ir divas preces ar atsvariem 3 un 4, un mugursomas svars ir 7. Mēs varam ielikt mugursomā 4. un 3. svara priekšmetu un atsvariem atbilstošā peļņa ir 2 un 3; tāpēc kopējā peļņa ir 5, tāpēc mēs pievienojam 5 pie M[2][7], kā parādīts zemāk:

Tagad “i” vērtība tiek palielināta un kļūst par 3.

Ja i = 3, W = 1

salīdzināms interfeiss java

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā komplektā ir trīs preces ar svariem 3, 4 un 5, un mugursomas svars ir 1. Mēs nevaram ievietot mugursomā nevienu no priekšmetiem, tāpēc pie M[3][ 1] parādīts šādi:

Ja i = 3, W = 2

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā komplektā ir trīs preces ar svaru 3, 4 un 5, un mugursomas svars ir 1. Mēs nevaram ievietot mugursomā nevienu no vienumiem, tāpēc mēs pievienojam 0 pie M[3][ 2] parādīts šādi:

Kad i = 3, W = 3

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā mums ir trīs preces, kuru svars ir attiecīgi 3, 4 un 5, un mugursomas svars ir 3. Preci ar svaru 3 var ievietot mugursomā, un precei atbilstošā peļņa ir 2, tāpēc mēs pievienojam 2 pie M[3][3], kā parādīts zemāk:

Ja i = 3, W = 4

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā mums ir trīs preces ar svaru attiecīgi 3, 4 un 5, un mugursomas svars ir 4. Mēs varam paturēt priekšmetu ar svaru 3 vai 4; peļņa (3), kas atbilst svaram 4, ir lielāka par peļņu, kas atbilst svaram 3, tāpēc mēs pievienojam 3 pie M[3][4], kā parādīts zemāk:

Kad i = 3, W = 5

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā mums ir trīs preces ar svaru attiecīgi 3, 4 un 5, un mugursomas svars ir 5. Mēs varam paturēt priekšmetu ar svaru 3, 4 vai 5; peļņa (3), kas atbilst svaram 4, ir lielāka nekā peļņa, kas atbilst svaram 3 un 5, tāpēc mēs pievienojam 3 pie M[3][5], kā parādīts zemāk:

Kad i = 3, W = 6

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā mums ir trīs preces ar svaru attiecīgi 3, 4 un 5, un mugursomas svars ir 6. Mēs varam paturēt priekšmetu ar svaru 3, 4 vai 5; peļņa (3), kas atbilst svaram 4, ir lielāka nekā peļņa, kas atbilst svaram 3 un 5, tāpēc mēs pievienojam 3 pie M[3][6], kā parādīts zemāk:

Kad i = 3, W = 7

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā mums ir trīs preces, kuru svars ir attiecīgi 3, 4 un 5, un mugursomas svars ir 7. Šajā gadījumā mēs varam paturēt gan preces ar svaru 3, gan 4, peļņas summa būtu vienāds ar (2 + 3), t.i., 5, tāpēc mēs pievienojam 5 pie M[3][7], kā parādīts zemāk:

Kad i = 3, W = 8

Svars, kas atbilst vērtībai 3, ir 5, t.i., w₃= 5. Tā kā mums ir trīs preces, kas ir attiecīgi 3., 4. un 5. svara komplektā, un mugursomas svars ir 8. Šajā gadījumā mēs varam paturēt gan 3., gan 4. svara priekšmetus, summa peļņa būtu vienāda ar (2 + 3), t.i., 5, tāpēc mēs pievienojam 5 pie M[3][8], kā parādīts zemāk:

Tagad “i” vērtība tiek palielināta un kļūst par 4.

Ja i = 4, W = 1

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četri priekšmeti attiecīgi 3, 4, 5 un 6 svaru komplektā un mugursomas svars ir 1. Visu priekšmetu svars ir lielāks par mugursomas svaru, tāpēc mēs nevaram pievienojiet jebkuru priekšmetu mugursomā; Tāpēc mēs pievienojam 0 pie M[4][1], kā parādīts zemāk:

Ja i = 4, W = 2

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četri priekšmeti attiecīgi 3, 4, 5 un 6 svaru komplektā un mugursomas svars ir 2. Visu priekšmetu svars ir lielāks par mugursomas svaru, tāpēc mēs nevaram pievienojiet jebkuru priekšmetu mugursomā; Tāpēc mēs pievienojam 0 pie M[4][2], kā parādīts zemāk:

Ja i = 4, W = 3

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četras preces svara komplektā attiecīgi 3, 4, 5 un 6, un mugursomas svars ir 3. Preci ar svaru 3 var ievietot mugursomā, un peļņa atbilst svars 4 ir 2, tāpēc mēs pievienosim 2 pie M[4][3], kā parādīts zemāk:

Ja i = 4, W = 4

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četras preces svara komplektā attiecīgi 3, 4, 5 un 6, un mugursomas svars ir 4. Preci ar svaru 4 var ievietot mugursomā, un peļņa atbilst svars 4 ir 3, tāpēc mēs pievienosim 3 pie M[4][4], kā parādīts tālāk:

Ja i = 4, W = 5

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četras preces svara komplektā attiecīgi 3, 4, 5 un 6, un mugursomas svars ir 5. Preci ar svaru 4 var ievietot mugursomā, un peļņa atbilst svars 4 ir 3, tāpēc mēs pievienosim 3 pie M[4][5], kā parādīts zemāk:

Ja i = 4, W = 6

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četri priekšmeti attiecīgi 3, 4, 5 un 6 svaru komplektā un mugursomas svars ir 6. Šajā gadījumā mēs varam ievietot priekšmetus mugursomā vai nu no svara 3, 4 , 5 vai 6, bet peļņa, t.i., 4, kas atbilst svaram 6, ir lielākā starp visām pozīcijām; tāpēc mēs pievienojam 4 pie M[4][6], kā parādīts zemāk:

Ja i = 4, W = 7

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četri vienumi attiecīgi 3., 4., 5. un 6. atsvaru komplektā un mugursomas svars ir 7. Šeit, ja mēs pievienosim divus svarus 3 un 4, tad tas radīs maksimumu. peļņa, t.i., (2 + 3) ir vienāds ar 5, tāpēc mēs pievienojam 5 pie M[4][7], kā parādīts zemāk:

Ja i = 4, W = 8

Svars, kas atbilst vērtībai 4, ir 6, t.i., w₄= 6. Tā kā mums ir četri priekšmeti attiecīgi 3, 4, 5 un 6 atsvaru komplektā un mugursomas svars ir 8. Šeit, ja mēs pievienosim divus svarus 3 un 4, tad tas radīs maksimumu. peļņa, t.i., (2 + 3) ir vienāds ar 5, tāpēc mēs pievienojam 5 pie M[4][8], kā parādīts zemāk:

java virknes formāts

Kā redzams tabulā, 5 ir maksimālā peļņa starp visiem ierakstiem. Rādītājs norāda uz pēdējo rindu un pēdējo kolonnu, kuras vērtība ir 5. Tagad mēs salīdzināsim 5 vērtību ar iepriekšējo rindu; ja iepriekšējā rindā, t.i., i = 3, ir tāda pati vērtība 5, rādītājs tiks pārvietots uz augšu. Tā kā iepriekšējā rindā ir vērtība 5, rādītājs tiks pārvietots uz augšu, kā parādīts tālāk esošajā tabulā:

Atkal mēs salīdzināsim vērtību 5 no iepriekš minētās rindas, t.i., i = 2. Tā kā iepriekšējā rindā ir vērtība 5, rādītājs atkal tiks pārvietots uz augšu, kā parādīts tālāk esošajā tabulā:

Atkal mēs salīdzināsim vērtību 5 no iepriekš minētās rindas, t.i., i = 1. Tā kā iepriekš minētajā rindā nav tādas pašas vērtības, mēs uzskatīsim, ka rinda i=1, un rindai atbilstošais svars ir 4. Tāpēc , mēs esam izvēlējušies svaru 4 un esam noraidījuši tālāk redzamos svarus 5 un 6:

x = {1, 0, 0}

Peļņa, kas atbilst svaram, ir 3. Tāpēc atlikušā peļņa (5 - 3) ir vienāda ar 2. Tagad mēs salīdzināsim šo vērtību 2 ar rindu i = 2. Tā kā rindā (i = 1) ir vērtība 2 ; tāpēc rādītājs tika pārvietots uz augšu, kā parādīts zemāk:

Atkal mēs salīdzinām vērtību 2 ar augstāk esošo rindu, t.i., i = 1. Tā kā rindā i =0 nav vērtības 2, tiks atlasīta rinda i = 1 un tiek parādīts svars, kas atbilst i = 1. zemāk:

X = {1, 1, 0, 0}

Peļņa, kas atbilst svaram, ir 2. Tāpēc atlikušā peļņa ir 0. Mēs salīdzinām 0 vērtību ar iepriekš minēto rindu. Tā kā iepriekš minētajā rindā ir 0 vērtība, bet šai rindai atbilstošā peļņa ir 0. Šajā uzdevumā ir atlasīti divi svari, t.i., 3 un 4, lai palielinātu peļņu.