Čia kuprinė yra kaip konteineris ar krepšys. Tarkime, kad pateikėme kai kuriuos elementus, kurie turi tam tikrą svorį arba pelną. Kai kuriuos daiktus turime įdėti į kuprinę taip, kad bendra vertė duotų maksimalų pelną.

Pavyzdžiui, konteinerio svoris yra 20 kg. Prekes turime parinkti taip, kad prekių svorio suma būtų arba mažesnė už konteinerio svorį arba lygi jam, o pelnas būtų maksimalus.

Yra dviejų tipų kuprinės problemos:

• 0/1 kuprinės problema
• Dalinės kuprinės problema

Abi problemas aptarsime po vieną. Pirmiausia sužinosime apie 0/1 kuprinės problemą.

Kas yra 0/1 kuprinės problema?

0/1 kuprinės problema reiškia, kad kuprinėje daiktai yra visiškai arba jokie daiktai nėra užpildyti. Pavyzdžiui, mes turime du elementus, kurių svoris yra atitinkamai 2 kg ir 3 kg. Jei renkamės 2kg prekę, tai negalime išsirinkti 1kg prekės iš 2kg prekės (prekė nedaloma); turime visiškai pasirinkti 2 kg prekę. Tai 0/1 kuprinės problema, kai mes arba visiškai išsirenkame prekę, arba pasirenkame tą prekę. 0/1 kuprinės problema išspręsta dinaminiu programavimu.

Kas yra dalinės kuprinės problema?

Dalinės kuprinės problema reiškia, kad galime padalinti daiktą. Pavyzdžiui, mes turime 3 kg prekę, tada galime pasiimti 2 kg prekę ir palikti 1 kg prekę. Dalinės kuprinės problema išspręsta taikant Greedy metodą.

0/1 kuprinės problemos pavyzdys.

Apsvarstykite problemą, kai svoriai ir pelnas yra:

Svoriai: {3, 4, 6, 5}

Pelnas: {2, 3, 1, 4}

Kuprinės svoris 8 kg

Prekių skaičius yra 4

Aukščiau pateiktą problemą galima išspręsti naudojant šį metodą:

x_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

hrithik roshan

= {0, 1, 0, 1}

Aukščiau pateikiami galimi deriniai. 1 reiškia, kad prekė yra visiškai paimta, o 0 reiškia, kad jokia prekė nepasirinkta. Kadangi yra 4 elementai, galimi deriniai bus:

2⁴= 16; Taigi. Yra 16 galimų derinių, kuriuos galima padaryti naudojant aukščiau pateiktą problemą. Sudarius visas kombinacijas, turime pasirinkti derinį, kuris duoda maksimalų pelną.

Kitas problemos sprendimo būdas yra dinaminis programavimo metodas. Taikant dinaminio programavimo metodą, sudėtinga problema suskirstoma į subproblemas, tada randame subproblemos sprendimą ir poproblemos sprendimas bus naudojamas sudėtingos problemos sprendimui rasti.

Kaip šią problemą galima išspręsti naudojant dinaminio programavimo metodą?

Pirmas,

Mes sukuriame matricą, kaip parodyta žemiau:

Aukščiau pateiktoje matricoje stulpeliai rodo svorį, t.y. 8. Eilutės rodo prekių pelną ir svorį. Čia mes neatsižvelgėme į svorį 8 tiesiogiai, problema suskirstyta į poproblemas, ty 0, 1, 2, 3, 4, 5, 6, 7, 8. ląstelės ir problemos atsakymas būtų saugomi galutiniame langelyje. Pirmiausia įrašome svorius didėjimo tvarka ir pelną pagal jų svorius, kaip parodyta toliau:

Į_i= {3, 4, 5, 6}

p_i= {2, 3, 4, 1}

Pirmoji eilutė ir pirmas stulpelis būtų 0, nes w=0 elemento nėra

Kai i=1, W=1

Į₁= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris yra 3, bet kuprinės talpa yra 1. Negalime užpildyti 3 kg prekės į 1 kg talpos kuprinę, todėl pridėkite 0 ties M[1][1], kaip parodyta žemiau :

Kai i = 1, W = 2

Į₁= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris yra 3, bet kuprinės talpa yra 2. Negalime užpildyti 3 kg prekės į 2 kg talpos kuprinę, todėl pridėkite 0 ties M[1][2], kaip parodyta žemiau :

Kai i=1, W=3

Į₁= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris lygus 3, o kuprinės svoris taip pat yra 3; todėl mes galime užpildyti kuprinę daiktu, kurio svoris lygus 3. Pelną, atitinkantį svorį 3, ty 2, M[1][3], kaip parodyta žemiau:

Kai i = 1, W = 4

_W1= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris lygus 3, o kuprinės svoris yra 4; todėl mes galime užpildyti kuprinę daiktu, kurio svoris lygus 3. Pelną, atitinkantį svorį 3, ty 2, M[1][4], kaip parodyta žemiau:

Kai i = 1, W = 5

_W1= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris lygus 3, o kuprinės svoris yra 5; todėl mes galime užpildyti kuprinę daiktu, kurio svoris lygus 3. Pelną, atitinkantį svorį 3, ty 2, M[1][5], kaip parodyta žemiau:

Kai i = 1, W = 6

_W1= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris lygus 3, o kuprinės svoris yra 6; todėl mes galime užpildyti kuprinę daiktu, kurio svoris lygus 3. Pelną, atitinkantį svorį 3, ty 2, M[1][6], kaip parodyta žemiau:

Kai i = 1, W = 7

_W1= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris lygus 3, o kuprinės svoris yra 7; todėl mes galime užpildyti kuprinę daiktu, kurio svoris lygus 3. Pelną, atitinkantį svorį 3, ty 2, M[1][7], kaip parodyta žemiau:

Kai i = 1, W = 8

_W1= 3; Kadangi rinkinyje turime tik vieną prekę, kurios svoris lygus 3, o kuprinės svoris yra 8; todėl mes galime užpildyti kuprinę daiktu, kurio svoris lygus 3. Pelną, atitinkantį svorį 3, ty 2, M[1][8], kaip parodyta žemiau:

Dabar „i“ reikšmė didėja ir tampa 2.

Kai i = 2, W = 1

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime tik vieną daiktą, kurio svoris lygus 4, o kuprinės svoris yra 1. Negalime dėti 4 svorio daikto į kuprinę, todėl prie M[2][1 pridedame 0 ] parodyta taip:

Kai i = 2, W = 2

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime tik vieną daiktą, kurio svoris lygus 4, o kuprinės svoris yra 2. Negalime dėti 4 svorio daikto į kuprinę, todėl prie M[2][2 pridedame 0 ] parodyta taip:

Kai i = 2, W = 3

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime du daiktus, kurių svoris yra 3 ir 4, o kuprinės svoris yra 3. Mes galime įdėti 3 svorio daiktą į kuprinę, todėl pridedame 2 prie M[2][3] parodyta taip:

Kai i = 2, W = 4

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime du daiktus, kurių svoris yra 3 ir 4, o kuprinės svoris yra 4. 4 svorio prekę galime dėti į kuprinę, nes pelnas, atitinkantis 4 svorį, yra didesnis nei prekės, turinčios svorį 3, todėl pridedame 3 prie M[2][4], kaip parodyta toliau:

Kai i = 2, W = 5

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime du daiktus, kurių svoris yra 3 ir 4, o kuprinės svoris yra 5. Į kuprinę galime įdėti 4 svorio prekę ir svorį atitinkantis pelnas yra 3, todėl pridedame 3 M[2][5] parodyta taip:

Kai i = 2, W = 6

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime du daiktus, kurių svoriai 3 ir 4, o kuprinės svoris yra 6. Į kuprinę galime įdėti 4 svorio prekę ir svorį atitinkantis pelnas yra 3, todėl pridedame 3 M[2][6] parodyta taip:

Kai i = 2, W = 7

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime du daiktus, kurių svoriai yra 3 ir 4, o kuprinės svoris yra 7. 4 ir 3 svorio prekę galime dėti į kuprinę ir pelnas, atitinkantis svorius, yra 2 ir 3; todėl bendras pelnas yra 5, todėl pridedame 5 prie M[2][7], kaip parodyta toliau:

Kai i = 2, W = 8

Svoris, atitinkantis 2 reikšmę, yra 4, t.y., w₂= 4. Kadangi rinkinyje turime du daiktus, kurių svoriai yra 3 ir 4, o kuprinės svoris yra 7. 4 ir 3 svorio prekę galime dėti į kuprinę ir pelnas, atitinkantis svorius, yra 2 ir 3; todėl bendras pelnas yra 5, todėl pridedame 5 prie M[2][7], kaip parodyta toliau:

Dabar „i“ reikšmė didėja ir tampa 3.

Kai i = 3, W = 1

sujungti rūšiavimo java

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi rinkinyje yra trys daiktai, kurių svoris yra 3, 4 ir 5, o kuprinės svoris yra 1. Negalime dėti nė vieno daikto į kuprinę, todėl prie M[3][ 1] parodyta taip:

Kai i = 3, W = 2

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi rinkinyje turime tris daiktus, kurių svoris yra 3, 4 ir 5, o kuprinės svoris yra 1. Negalime dėti nė vieno daikto į kuprinę, todėl prie M[3][ 2] parodyta taip:

Kai i = 3, W = 3

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi mes turime tris daiktus atitinkamai 3, 4 ir 5 svorio rinkinyje, o kuprinės svoris yra 3. Prekę, kurios svoris 3, galima įdėti į kuprinę ir pelnas, atitinkantis prekę, yra 2, todėl pridedame 2 prie M[3][3], kaip parodyta toliau:

Kai i = 3, W = 4

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi mes turime tris daiktus atitinkamai 3, 4 ir 5 svorio rinkinyje, o kuprinės svoris yra 4. Galime pasilikti 3 arba 4 svorio prekę; pelnas (3), atitinkantis svorį 4, yra didesnis nei pelnas, atitinkantis svorį 3, todėl pridedame 3 prie M[3][4], kaip parodyta toliau:

Kai i = 3, W = 5

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi mes turime tris daiktus, kurių svoris atitinkamai 3, 4 ir 5, o kuprinės svoris yra 5. Galime pasilikti 3, 4 arba 5 svorio prekę; pelnas (3), atitinkantis svorį 4, yra didesnis nei pelnas, atitinkantis svorius 3 ir 5, todėl prie M[3][5] pridedame 3, kaip parodyta toliau:

Kai i = 3, W = 6

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi mes turime tris daiktus, kurių svoris atitinkamai 3, 4 ir 5, o kuprinės svoris yra 6. Galime pasilikti 3, 4 arba 5 svorio prekę; pelnas (3), atitinkantis svorį 4, yra didesnis nei pelnas, atitinkantis svorius 3 ir 5, todėl prie M[3][6] pridedame 3, kaip parodyta toliau:

Kai i = 3, W = 7

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi atitinkamai 3, 4 ir 5 svorio rinkinyje turime tris daiktus, o kuprinės svoris yra 7. Šiuo atveju galime pasilikti ir 3, ir 4 svorio prekes, pelno sumą būtų lygus (2 + 3), ty 5, todėl prie M[3][7] pridedame 5, kaip parodyta toliau:

Kai i = 3, W = 8

Svoris, atitinkantis reikšmę 3, yra 5, t.y., w₃= 5. Kadangi mes turime tris daiktus atitinkamai 3, 4 ir 5 svorio rinkinyje, o kuprinės svoris yra 8. Šiuo atveju galime pasilikti ir 3, ir 4 svorio daiktus, tai suma pelnas būtų lygus (2 + 3), ty 5, todėl prie M[3][8] pridedame 5, kaip parodyta toliau:

Dabar „i“ reikšmė didėja ir tampa 4.

Kai i = 4, W = 1

Svoris, atitinkantis 4 reikšmę, yra 6, t.y., w₄= 6. Kadangi mes turime keturis daiktus atitinkamai 3, 4, 5 ir 6 svorių rinkinyje, o kuprinės svoris yra 1. Visų daiktų svoris yra didesnis už kuprinės svorį, todėl negalime įdėkite bet kokį daiktą į kuprinę; Todėl prie M[4][1] pridedame 0, kaip parodyta toliau:

Kai i = 4, W = 2

Svoris, atitinkantis 4 reikšmę, yra 6, t.y., w₄= 6. Kadangi mes turime keturis daiktus atitinkamai 3, 4, 5 ir 6 svorių rinkinyje, o kuprinės svoris yra 2. Visų daiktų svoris yra didesnis už kuprinės svorį, todėl negalime įdėkite bet kokį daiktą į kuprinę; Todėl prie M[4][2] pridedame 0, kaip parodyta toliau:

Kai i = 4, W = 3

Svoris, atitinkantis reikšmę 4, yra 6, t.y., w₄= 6. Kadangi mes turime keturias prekes atitinkamai 3, 4, 5 ir 6 svorių rinkinyje, o kuprinės svoris yra 3. Prekė, kurios svoris 3, gali būti įdėta į kuprinę ir pelnas atitinka 4 svoris yra 2, todėl pridėsime 2 ties M[4][3], kaip parodyta toliau:

Kai i = 4, W = 4

Svoris, atitinkantis reikšmę 4, yra 6, t.y., w₄= 6. Kadangi turime keturias prekes atitinkamai 3, 4, 5 ir 6 svorių rinkinyje, o kuprinės svoris yra 4. Prekė, kurios svoris 4, gali būti įdėta į kuprinę ir pelnas atitinka 4 svoris yra 3, todėl pridėsime 3 ties M[4][4], kaip parodyta toliau:

Kai i = 4, W = 5

Svoris, atitinkantis reikšmę 4, yra 6, t.y., w₄= 6. Kadangi mes turime keturias prekes atitinkamai svorių 3, 4, 5 ir 6 rinkinyje, o kuprinės svoris yra 5. Prekė, kurios svoris 4, gali būti įdėta į kuprinę ir pelnas atitinka 4 svoris yra 3, todėl pridėsime 3 ties M[4][5], kaip parodyta toliau:

Kai i = 4, W = 6

Svoris, atitinkantis reikšmę 4, yra 6, t.y., w₄= 6. Kadangi atitinkamai 3, 4, 5 ir 6 svorių rinkinyje turime keturis daiktus, o kuprinės svoris yra 6. Šiuo atveju daiktus į kuprinę galime dėti 3, 4 , 5 arba 6, bet pelnas, t. y. 4, atitinkantis svorį 6, yra didžiausias tarp visų prekių; todėl prie M[4][6] pridedame 4, kaip parodyta toliau:

java poeilutės metodas

Kai i = 4, W = 7

Svoris, atitinkantis reikšmę 4, yra 6, t.y., w₄= 6. Kadangi mes turime keturis elementus atitinkamai 3, 4, 5 ir 6 svorių rinkinyje, o kuprinės svoris yra 7. Čia, jei pridėsime du svorius 3 ir 4, tada bus gauta daugiausia pelnas, ty (2 + 3) lygus 5, todėl prie M[4][7] pridedame 5, kaip parodyta toliau:

Kai i = 4, W = 8

Svoris, atitinkantis reikšmę 4, yra 6, t.y., w₄= 6. Kadangi mes turime keturis elementus atitinkamai 3, 4, 5 ir 6 svorių rinkinyje, o kuprinės svoris yra 8. Čia, jei pridėsime du svorius 3 ir 4, tada bus gauta daugiausia pelnas, ty (2 + 3) lygus 5, todėl prie M[4][8] pridedame 5, kaip parodyta toliau:

Kaip matome aukščiau esančioje lentelėje, 5 yra didžiausias pelnas tarp visų įrašų. Rodyklė nurodo paskutinę eilutę ir paskutinį stulpelį, turintį 5 ​​reikšmę. Dabar palyginsime 5 reikšmę su ankstesne eilute; jei ankstesnėje eilutėje, ty i = 3, yra ta pati reikšmė 5, tada rodyklė pasislinks aukštyn. Kadangi ankstesnėje eilutėje yra reikšmė 5, žymeklis bus perkeltas aukštyn, kaip parodyta toliau esančioje lentelėje:

Vėlgi, palyginsime 5 reikšmę iš aukščiau pateiktos eilutės, t. y. i = 2. Kadangi aukščiau esančioje eilutėje yra reikšmė 5, žymeklis vėl bus perkeltas aukštyn, kaip parodyta toliau esančioje lentelėje:

Vėlgi, palyginsime 5 reikšmę iš aukščiau pateiktos eilutės, ty i = 1. Kadangi aukščiau esančioje eilutėje nėra tos pačios reikšmės, laikysime eilutę i=1, o eilutę atitinkantis svoris yra 4. , pasirinkome svorį 4 ir atmetėme toliau pateiktus svorius 5 ir 6:

x = { 1, 0, 0}

Pelnas, atitinkantis svorį, yra 3. Todėl likęs pelnas yra (5 - 3) lygus 2. Dabar palyginsime šią reikšmę 2 su eilute i = 2. Kadangi eilutėje (i = 1) yra reikšmė 2 ; todėl rodyklė pasislinko aukštyn, kaip parodyta žemiau:

Vėlgi, lyginame 2 reikšmę su aukščiau esančia eilute, t. y. i = 1. Kadangi eilutėje i = 0 nėra reikšmės 2, bus pasirinkta eilutė i = 1 ir rodomas svoris, atitinkantis i = 1. žemiau:

X = {1, 1, 0, 0}

Svorį atitinkantis pelnas yra 2. Todėl likęs pelnas yra 0. 0 reikšmę lyginame su aukščiau pateikta eilute. Kadangi aukščiau esančioje eilutėje yra 0 reikšmė, bet šią eilutę atitinkantis pelnas yra 0. Šioje užduotyje pasirenkami du svoriai, ty 3 ir 4, kad būtų padidintas pelnas.