TechCodeview

Овде је ранац као контејнер или торба. Претпоставимо да смо дали неке ставке које имају неку тежину или профит. Неке ствари морамо ставити у ранац на начин да укупна вредност произведе максималан профит.

На пример, тежина контејнера је 20 кг. Ставке морамо одабрати на начин да збир тежине предмета буде мањи или једнак тежини контејнера, а профит максималан.

Постоје две врсте проблема са ранцем:

• 0/1 проблем са ранцем
• Проблем фракционог ранца

Разговараћемо о оба проблема један по један. Прво ћемо научити о проблему ранца 0/1.

Шта је проблем 0/1 ранца?

Проблем са ранцем 0/1 значи да су предмети или у потпуности или да ниједан предмет није попуњен у ранцу. На пример, имамо два предмета тежине 2 кг и 3 кг, респективно. Ако одаберемо артикал од 2кг, онда не можемо изабрати ставку од 1кг од предмета од 2кг (ставка није дељива); морамо у потпуности да покупимо предмет од 2 кг. Ово је проблем ранца 0/1 у којем или бирамо предмет у потпуности или ћемо га изабрати. Проблем ранца 0/1 је решен динамичким програмирањем.

Шта је проблем фракционог ранца?

Проблем фракционог ранца значи да можемо да поделимо предмет. На пример, имамо артикал од 3 кг, онда можемо изабрати предмет од 2 кг и оставити предмет од 1 кг. Проблем фракционог ранца је решен похлепним приступом.

Пример проблема 0/1 ранца.

Узмите у обзир проблем када су тежине и профити:

Тежина: {3, 4, 6, 5}

Добит: {2, 3, 1, 4}

Тежина ранца је 8 кг

Број предмета је 4

Горњи проблем се може решити коришћењем следеће методе:

Икс_и= {1, 0, 0, 1}

= {0, 0, 0, 1}

пример листе у Јави

= {0, 1, 0, 1}

Горе наведене су могуће комбинације. 1 означава да је ставка у потпуности изабрана, а 0 значи да ниједна ставка није изабрана. Пошто постоје 4 ставке, могуће комбинације ће бити:

2⁴= 16; Тако. Постоји 16 могућих комбинација које се могу направити коришћењем горњег проблема. Када су све комбинације направљене, морамо одабрати комбинацију која даје максималан профит.

Други приступ решавању проблема је приступ динамичком програмирању. У приступу динамичког програмирања, компликовани проблем се дели на подпроблеме, затим се налази решење подпроблема и решење подпроблема ће се користити за проналажење решења сложеног проблема.

Како се овај проблем може решити коришћењем приступа динамичког програмирања?

Први,

креирамо матрицу као што је приказано у наставку:

У горњој матрици, колоне представљају тежину, тј. 8. Редови представљају профит и тежину ставки. Овде нисмо директно узели тежину 8, проблем је подељен на подпроблеме, тј. 0, 1, 2, 3, 4, 5, 6, 7, 8. Решење подпроблема би било сачувано у ћелије и одговор на проблем биће сачуван у последњој ћелији. Прво, пишемо пондере у растућем редоследу и профит према њиховим тежинама приказаним у наставку:

Ин_и= {3, 4, 5, 6}

стр_и= {2, 3, 4, 1}

Први ред и прва колона би били 0 јер не постоји ставка за в=0

Када је и=1, В=1

Ин₁= 3; Пошто имамо само један предмет у комплету који има тежину 3, али је капацитет ранца 1. Не можемо да попунимо предмет од 3кг у ранац капацитета 1 кг, па додајте 0 на М[1][1] приказаном испод :

Када је и = 1, В = 2

Ин₁= 3; Пошто имамо само један предмет у сету који има тежину 3, али је капацитет ранца 2. Не можемо да попунимо предмет од 3кг у ранац капацитета 2 кг, па додајте 0 на М[1][2] приказаном испод :

Када је и=1, В=3

Ин₁= 3; Пошто у комплету имамо само један предмет чија је тежина једнака 3, а тежина ранца је такође 3; стога, ранац можемо напунити предметом тежине једнаком 3. Стављамо профит који одговара тежини 3, тј. 2 на М[1][3] приказаном испод:

Када је и=1, В = 4

_В1= 3; Пошто у комплету имамо само један предмет чија је тежина једнака 3, а тежина ранца је 4; стога, ранац можемо напунити предметом тежине једнаком 3. Стављамо профит који одговара тежини 3, тј. 2 на М[1][4] приказаном испод:

Када је и=1, В = 5

_В1= 3; Пошто у комплету имамо само један предмет чија је тежина једнака 3, а тежина ранца је 5; стога, ранац можемо напунити предметом тежине једнаком 3. Стављамо профит који одговара тежини 3, тј. 2 на М[1][5] приказаном испод:

Када је и =1, В=6

_В1= 3; Пошто у комплету имамо само један предмет чија је тежина једнака 3, а тежина ранца је 6; стога, ранац можемо напунити предметом тежине једнаком 3. Стављамо профит који одговара тежини 3, тј. 2 на М[1][6] приказаном испод:

Када је и=1, В = 7

_В1= 3; Пошто у комплету имамо само један предмет чија је тежина једнака 3, а тежина ранца је 7; стога, ранац можемо напунити предметом тежине једнаком 3. Стављамо профит који одговара тежини 3, тј. 2 на М[1][7] приказаном испод:

Када је и =1, В =8

_В1= 3; Пошто у комплету имамо само један предмет чија је тежина једнака 3, а тежина ранца је 8; стога, ранац можемо напунити предметом тежине једнаком 3. Стављамо профит који одговара тежини 3, тј. 2 на М[1][8] приказаном испод:

Сада се вредност 'и' повећава и постаје 2.

Када је и =2, В = 1

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто имамо само један предмет у сету чија је тежина једнака 4, а тежина ранца је 1. Предмет тежине 4 не можемо ставити у ранац, па додајемо 0 на М[2][1 ] приказан као доле:

Када је и =2, В = 2

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто имамо само један предмет у сету чија је тежина једнака 4, а тежина ранца је 2. Предмет тежине 4 не можемо ставити у ранац, па додајемо 0 на М[2][2 ] приказан као доле:

Када је и =2, В = 3

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто у сету имамо два предмета који имају тежине 3 и 4, а тежина ранца је 3. Предмет тежине 3 можемо ставити у ранац, па додајемо 2 на М[2][3] приказано као доле:

Када је и =2, В = 4

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто имамо два предмета у комплету који имају тежину 3 и 4, а тежина ранца је 4. Предмет тежине 4 можемо ставити у ранац јер је профит који одговара тежини 4 већи од предмета који има тежину 3, па додајемо 3 на М[2][4] приказано на доле:

Када је и = 2, В = 5

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто имамо два предмета у сету који имају тежине 3 и 4, а тежина ранца је 5. Предмет тежине 4 можемо ставити у ранац и добитак који одговара тежини је 3, па додајемо 3 на М[2][5] приказано испод:

Када је и = 2, В = 6

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто у сету имамо два предмета који имају тежине 3 и 4, а тежина ранца је 6. Предмет тежине 4 можемо ставити у ранац и добитак који одговара тежини је 3, па додајемо 3 на М[2][6] приказано доле:

Када је и = 2, В = 7

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто имамо два предмета у сету који имају тежину 3 и 4, а тежина ранца је 7. Ставке тежине 4 и 3 можемо ставити у ранац и добици који одговарају тежинама су 2 и 3; према томе, укупан профит је 5, тако да додајемо 5 на М[2][7] како је приказано испод:

Када је и = 2, В = 8

Тежина која одговара вредности 2 је 4, тј. в₂= 4. Пошто имамо два предмета у сету који имају тежину 3 и 4, а тежина ранца је 7. Ставке тежине 4 и 3 можемо ставити у ранац и добици који одговарају тежинама су 2 и 3; према томе, укупан профит је 5, тако да додајемо 5 на М[2][7] како је приказано испод:

Сада се вредност 'и' повећава и постаје 3.

Када је и = 3, В = 1

замењивање метода у Јави

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у сету који имају тежине 3, 4 и 5, а тежина ранца је 1. Не можемо ставити ниједан од предмета у ранац, па додајемо 0 на М[3][ 1] приказан као доле:

Када је и = 3, В = 2

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у сету који имају тежину 3, 4 и 5, а тежина ранца је 1. Не можемо ставити ниједан од предмета у ранац, па додајемо 0 на М[3][ 2] приказан као доле:

Када је и = 3, В = 3

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у скупу тежине 3, 4, и 5 респективно и тежина ранца је 3. Предмет тежине 3 може се ставити у ранац и добитак који одговара предмету је 2, па додајемо 2 на М[3][3] приказано на доле:

Када је и = 3, В = 4

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у скупу тежине 3, 4, односно 5, а тежина ранца је 4. Можемо задржати предмет тежине 3 или 4; профит (3) који одговара тежини 4 је већи од профита који одговара тежини 3, тако да додајемо 3 на М[3][4] приказаном испод:

Када је и = 3, В = 5

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у скупу тежине 3, 4, односно 5, а тежина ранца је 5. Можемо задржати предмет тежине 3, 4 или 5; профит (3) који одговара тежини 4 је већи од профита који одговара тежини 3 и 5, тако да додајемо 3 на М[3][5] приказаном испод:

Када је и =3, В = 6

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у скупу тежине 3, 4, односно 5, а тежина ранца је 6. Можемо задржати предмет тежине 3, 4 или 5; профит (3) који одговара тежини 4 је већи од профита који одговара тежини 3 и 5, тако да додајемо 3 на М[3][6] као што је приказано у наставку:

Када је и =3, В = 7

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у скупу тежине 3, 4 и 5, а тежина ранца је 7. У овом случају можемо задржати оба предмета тежине 3 и 4, збир профита би било једнако (2 + 3), тј. 5, тако да додајемо 5 на М[3][7] као што је приказано испод:

Када је и = 3, В = 8

преоптерећење метода

Тежина која одговара вредности 3 је 5, тј. в₃= 5. Пошто имамо три предмета у скупу тежине 3, 4, односно 5, а тежина ранца је 8. У овом случају можемо задржати оба предмета тежине 3 и 4, збир профит би био једнак (2 + 3), тј. 5, тако да додајемо 5 на М[3][8] као што је приказано испод:

Сада се вредност 'и' повећава и постаје 4.

Када је и = 4, В = 1

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 1. Тежина свих предмета је већа од тежине ранца, тако да не можемо додајте било који предмет у ранац; Према томе, додајемо 0 на М[4][1] приказано на доле:

Када је и = 4, В = 2

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 2. Тежина свих предмета је већа од тежине ранца, тако да не можемо додајте било који предмет у ранац; Према томе, додајемо 0 на М[4][2] приказано на доле:

Када је и = 4, В = 3

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 3. Предмет са тежином 3 може се ставити у ранац и добит одговара тежина 4 је 2, тако да ћемо додати 2 на М[4][3] као што је приказано испод:

Када је и = 4, В = 4

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 4. Предмет тежине 4 може се ставити у ранац и добит одговара тежина 4 је 3, тако да ћемо додати 3 на М[4][4] као што је приказано испод:

Када је и = 4, В = 5

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 5. Предмет са тежином 4 може се ставити у ранац и добит одговара тежина 4 је 3, тако да ћемо додати 3 на М[4][5] као што је приказано испод:

Када је и = 4, В = 6

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежине 3, 4, 5, и 6 респективно, а тежина ранца је 6. У овом случају, предмете можемо ставити у ранац било који од тежине 3, 4 , 5 или 6 али је профит, тј. 4 који одговара тежини 6, највећи међу свим ставкама; стога, додајемо 4 на М[4][6] приказано на доле:

Када је и = 4, В = 7

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 7. Овде, ако додамо два предмета тежине 3 и 4 онда ће се произвести максимум профит, тј. (2 + 3) је једнако 5, тако да додајемо 5 на М[4][7] као што је приказано испод:

Када је и = 4, В = 8

Тежина која одговара вредности 4 је 6, тј. в₄= 6. Пошто имамо четири предмета у скупу тежина 3, 4, 5 и 6 респективно, а тежина ранца је 8. Овде, ако додамо два предмета тежине 3 и 4 онда ће се произвести максимум профит, тј. (2 + 3) је једнако 5, тако да додајемо 5 на М[4][8] као што је приказано испод:

Као што можемо приметити у горњој табели да је 5 максимални профит међу свим уносима. Показивач показује на последњи ред и последњу колону са 5 вредности. Сада ћемо упоредити вредност 5 са ​​претходним редом; ако претходни ред, тј. и = 3, садржи исту вредност 5, показивач ће се померити нагоре. Пошто претходни ред садржи вредност 5, показивач ће бити померен нагоре као што је приказано у табели испод:

Поново ћемо упоредити вредност 5 из горњег реда, тј. и = 2. Пошто горњи ред садржи вредност 5, показивач ће поново бити померен нагоре као што је приказано у табели испод:

Поново ћемо упоредити вредност 5 из горњег реда, тј. и = 1. Пошто горњи ред не садржи исту вредност, размотрићемо ред и=1, а тежина која одговара реду је 4. Према томе, ред изнад је 4. , изабрали смо тежину 4 и одбацили смо тежине 5 и 6 приказане испод:

к = { 1, 0, 0}

Добит која одговара тежини је 3. Дакле, преостали профит је (5 - 3) једнак 2. Сада ћемо упоредити ову вредност 2 са редом и = 2. Пошто ред (и = 1) садржи вредност 2 ; стога, показивач се померио нагоре приказано испод:

Поново поредимо вредност 2 са горњим редом, тј. и = 1. Пошто ред и =0 не садржи вредност 2, тако ће бити изабран ред и = 1 и приказана је тежина која одговара и = 1 3 испод:

Кс = {1, 1, 0, 0}

Добит која одговара тежини је 2. Према томе, преостали профит је 0. Упоређујемо вредност 0 са горњим редом. Пошто горњи ред садржи вредност 0, али је профит који одговара овом реду 0. У овом задатку су изабране две тежине, тј. 3 и 4 да би се максимизирао профит.