Тук раницата е като контейнер или чанта. Да предположим, че сме дали някои елементи, които имат някакви тегла или печалби. Трябва да поставим някои предмети в раницата по такъв начин, че общата стойност да генерира максимална печалба.

Например, теглото на контейнера е 20 кг. Трябва да подберем артикулите по такъв начин, че сборът от теглото на артикулите да бъде по-малък или равен на теглото на контейнера, а печалбата да е максимална.

Има два вида проблеми с раницата:

• 0/1 проблем с раницата
• Проблем с частична раница

Ще обсъдим двата проблема един по един. Първо ще научим за проблема с раницата 0/1.

Какъв е проблемът с раницата 0/1?

Проблемът с раницата 0/1 означава, че артикулите са или напълно, или никакви артикули не са пълни в раницата. Например, имаме два елемента с тегло съответно 2 кг и 3 кг. Ако изберем артикул от 2 кг, тогава не можем да изберем артикул от 1 кг от артикул от 2 кг (артикулът не се дели); трябва да изберем напълно артикула от 2 кг. Това е проблем с раница 0/1, при който или избираме предмета изцяло, или ще вземем този предмет. Проблемът с раницата 0/1 се решава чрез динамично програмиране.

Какъв е проблемът с частичната раница?

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

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

Помислете за проблема с теглата и печалбите са:

Грамажи: {3, 4, 6, 5}

Печалби: {2, 3, 1, 4}

Теглото на раницата е 8 кг

Броят на артикулите е 4

Горният проблем може да бъде решен чрез използване на следния метод:

х_аз= {1, 0, 0, 1}

= {0, 0, 0, 1}

c програма за двумерен масив

= {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, тъй като няма елемент за w=0

Когато i=1, W=1

в₁= 3; Тъй като имаме само един артикул в комплекта с тегло 3, но капацитетът на раницата е 1. Не можем да напълним артикул от 3 кг в раница с капацитет 1 кг, така че добавете 0 към M[1][1], както е показано по-долу :

Когато i = 1, W = 2

в₁= 3; Тъй като имаме само един артикул в комплекта с тегло 3, но капацитетът на раницата е 2. Не можем да напълним артикул от 3 кг в раница с капацитет 2 кг, така че добавете 0 към M[1][2], както е показано по-долу :

Когато i=1, W=3

в₁= 3; Тъй като имаме само един елемент в комплекта с тегло, равно на 3, и теглото на раницата също е 3; следователно можем да напълним раницата с артикул с тегло равно на 3. Поставяме печалба, съответстваща на тегло 3, т.е. 2 при M[1][3], както е показано по-долу:

Когато i=1, W=4

_W1= 3; Тъй като имаме само един артикул в комплекта с тегло равно на 3, а теглото на раницата е 4; следователно можем да напълним раницата с артикул с тегло, равно на 3. Поставяме печалба, съответстваща на тегло 3, т.е. 2 при M[1][4], както е показано по-долу:

Когато i=1, W = 5

_W1= 3; Тъй като имаме само един артикул в комплекта с тегло равно на 3, а теглото на раницата е 5; следователно можем да напълним раницата с предмет с тегло, равно на 3. Поставяме печалба, съответстваща на тегло 3, т.е. 2 при M[1][5], както е показано по-долу:

Когато i =1, W=6

_W1= 3; Тъй като имаме само един елемент в комплекта с тегло, равно на 3, а теглото на раницата е 6; следователно можем да напълним раницата с артикул с тегло, равно на 3. Поставяме печалба, съответстваща на тегло 3, т.е. 2 при M[1][6], както е показано по-долу:

Когато i=1, W=7

_W1= 3; Тъй като имаме само един елемент в комплекта с тегло, равно на 3, а теглото на раницата е 7; следователно можем да напълним раницата с артикул с тегло, равно на 3. Поставяме печалба, съответстваща на тегло 3, т.е. 2 при M[1][7], както е показано по-долу:

Когато i =1, W =8

_W1= 3; Тъй като имаме само един елемент в комплекта с тегло равно на 3, а теглото на раницата е 8; следователно можем да напълним раницата с предмет с тегло, равно на 3. Поставяме печалба, съответстваща на тегло 3, т.е. 2 при M[1][8], както е показано по-долу:

Сега стойността на 'i' се увеличава и става 2.

Когато i =2, W = 1

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме само един артикул в комплекта с тегло равно на 4, а теглото на раницата е 1. Не можем да поставим артикул с тегло 4 в раница, така че добавяме 0 към M[2][1 ] показано по-долу:

Когато i =2, W = 2

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме само един артикул в комплекта с тегло равно на 4, а теглото на раницата е 2. Не можем да поставим артикул с тегло 4 в раница, така че добавяме 0 към M[2][2 ] показано по-долу:

Когато i =2, W = 3

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме два артикула в комплекта с тегла 3 и 4, а теглото на раницата е 3. Можем да поставим артикула с тегло 3 в раница, така че добавяме 2 към M[2][3] показано по-долу:

Когато i =2, W = 4

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме два елемента в комплекта с тегла 3 и 4, а теглото на раницата е 4. Можем да поставим артикул с тегло 4 в раница, тъй като печалбата, съответстваща на тегло 4, е по-голяма от артикула с тегло 3, така че добавяме 3 към M[2][4], както е показано по-долу:

Когато i = 2, W = 5

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме два артикула в комплекта с тегла 3 и 4, а теглото на раницата е 5. Можем да поставим артикул с тегло 4 в раница и печалбата, съответстваща на теглото, е 3, така че добавяме 3 към M[2][5] е показано по-долу:

Когато i = 2, W = 6

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме два артикула в комплекта с тегла 3 и 4, а теглото на раницата е 6. Можем да поставим артикул с тегло 4 в раница и печалбата, съответстваща на теглото, е 3, така че добавяме 3 към M[2][6] показан по-долу:

Когато i = 2, W = 7

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме два елемента в комплекта с тегла 3 и 4, а теглото на раницата е 7. Можем да поставим артикул с тегло 4 и 3 в раница и печалбите, съответстващи на теглата, са 2 и 3; следователно общата печалба е 5, така че добавяме 5 към M[2][7], както е показано по-долу:

Когато i = 2, W = 8

Теглото, съответстващо на стойността 2, е 4, т.е₂= 4. Тъй като имаме два елемента в комплекта с тегла 3 и 4, а теглото на раницата е 7. Можем да поставим артикул с тегло 4 и 3 в раница и печалбите, съответстващи на теглата, са 2 и 3; следователно общата печалба е 5, така че добавяме 5 към M[2][7], както е показано по-долу:

Сега стойността на 'i' се увеличава и става 3.

Когато i = 3, W = 1

математически клас java

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта с тегла 3, 4 и 5, а теглото на раницата е 1. Не можем да поставим нито един от артикулите в раница, затова добавяме 0 към M[3][ 1] показан по-долу:

Когато i = 3, W = 2

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта с тегло 3, 4 и 5, а теглото на раницата е 1. Не можем да поставим нито един от артикулите в раница, така че добавяме 0 към M[3][ 2] показан по-долу:

Когато i = 3, W = 3

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта съответно с тегло 3, 4 и 5 и теглото на раницата е 3. Артикулът с тегло 3 може да бъде поставен в раницата и печалбата, съответстваща на артикула, е 2, така че добавяме 2 към M[3][3], както е показано по-долу:

Когато i = 3, W = 4

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта съответно с тегло 3, 4 и 5, а теглото на раницата е 4. Можем да запазим артикула с тегло 3 или 4; печалбата (3), съответстваща на тегло 4, е по-голяма от печалбата, съответстваща на тегло 3, така че добавяме 3 към M[3][4], както е показано по-долу:

Когато i = 3, W = 5

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта съответно с тегло 3, 4 и 5, а теглото на раницата е 5. Можем да запазим артикула с тегло 3, 4 или 5; печалбата (3), съответстваща на тегло 4, е повече от печалбите, съответстващи на тегло 3 и 5, така че добавяме 3 към M[3][5], както е показано по-долу:

fmovies

Когато i =3, W = 6

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта съответно с тегло 3, 4 и 5, а теглото на раницата е 6. Можем да запазим артикула с тегло 3, 4 или 5; печалбата (3), съответстваща на тегло 4, е повече от печалбите, съответстващи на тегло 3 и 5, така че добавяме 3 към M[3][6], както е показано по-долу:

Когато i =3, W = 7

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта съответно с тегло 3, 4 и 5, а теглото на раницата е 7. В този случай можем да запазим и двата елемента с тегло 3 и 4, сумата от печалбата ще бъде равно на (2 + 3), т.е. 5, така че добавяме 5 към M[3][7], както е показано по-долу:

Когато i = 3, W = 8

Теглото, съответстващо на стойността 3, е 5, т.е. w₃= 5. Тъй като имаме три артикула в комплекта съответно с тегло 3, 4 и 5, а теглото на раницата е 8. В този случай можем да запазим и двата елемента с тегло 3 и 4, сумата от печалбата ще бъде равна на (2 + 3), т.е. 5, така че добавяме 5 към M[3][8], както е показано по-долу:

Сега стойността на 'i' се увеличава и става 4.

Когато i = 4, W = 1

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в набора от тегла съответно 3, 4, 5 и 6, а теглото на раницата е 1. Теглото на всички артикули е по-голямо от теглото на раницата, така че не можем добавете всеки предмет в раницата; Следователно добавяме 0 към M[4][1], както е показано по-долу:

Когато i = 4, W = 2

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в комплекта с тегла съответно 3, 4, 5 и 6, а теглото на раницата е 2. Теглото на всички артикули е по-голямо от теглото на раницата, така че не можем добавете всеки предмет в раницата; Следователно добавяме 0 към M[4][2], както е показано по-долу:

Когато i = 4, W = 3

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в комплекта съответно с тегла 3, 4, 5 и 6, а теглото на раницата е 3. Артикулът с тегло 3 може да бъде поставен в раницата и печалбата, съответстваща на тегло 4 е 2, така че ще добавим 2 към M[4][3], както е показано по-долу:

Когато i = 4, W = 4

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в набора съответно с тегла 3, 4, 5 и 6, а теглото на раницата е 4. Артикулът с тегло 4 може да бъде поставен в раницата и печалбата, съответстваща на тегло 4 е 3, така че ще добавим 3 към M[4][4], както е показано по-долу:

Когато i = 4, W = 5

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в комплекта съответно с тегла 3, 4, 5 и 6, а теглото на раницата е 5. Артикулът с тегло 4 може да бъде поставен в раницата и печалбата, съответстваща на тегло 4 е 3, така че ще добавим 3 към M[4][5], както е показано по-долу:

Когато i = 4, W = 6

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в набора съответно с тегла 3, 4, 5 и 6, а теглото на раницата е 6. В този случай можем да поставим артикулите в раницата с тегло 3, 4 , 5 или 6, но печалбата, т.е. 4, съответстваща на тегло 6, е най-висока сред всички елементи; следователно добавяме 4 към M[4][6], както е показано по-долу:

Когато i = 4, W = 7

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в набора съответно с тегла 3, 4, 5 и 6, а теглото на раницата е 7. Тук, ако добавим два артикула с тегла 3 и 4, тогава ще се получи максималното печалба, т.е. (2 + 3) е равно на 5, така че добавяме 5 към M[4][7], както е показано по-долу:

Когато i = 4, W = 8

Теглото, съответстващо на стойността 4, е 6, т.е₄= 6. Тъй като имаме четири артикула в набора съответно с тегла 3, 4, 5 и 6, а теглото на раницата е 8. Тук, ако добавим два артикула с тегла 3 и 4, тогава ще се получи максималното печалба, т.е. (2 + 3) е равно на 5, така че добавяме 5 към M[4][8], както е показано по-долу:

Както можем да видим в горната таблица, 5 е максималната печалба сред всички записи. Указателят сочи към последния ред и последната колона със стойност 5. Сега ще сравним стойността 5 с предишния ред; ако предишният ред, т.е. i = 3, съдържа същата стойност 5, тогава показалецът ще се измести нагоре. Тъй като предишният ред съдържа стойност 5, показалецът ще бъде изместен нагоре, както е показано в таблицата по-долу:

Отново ще сравним стойността 5 от горния ред, т.е. i = 2. Тъй като горният ред съдържа стойност 5, показалецът отново ще бъде изместен нагоре, както е показано в таблицата по-долу:

Отново ще сравним стойността 5 от горния ред, т.е. i = 1. Тъй като горният ред не съдържа същата стойност, ще разгледаме реда i=1 и теглото, съответстващо на реда, е 4. Следователно , избрахме тегло 4 и отхвърлихме теглата 5 и 6, показани по-долу:

x = { 1, 0, 0}

Печалбата, съответстваща на теглото, е 3. Следователно, оставащата печалба е (5 - 3), равна на 2. Сега ще сравним тази стойност 2 с реда i = 2. Тъй като редът (i = 1) съдържа стойността 2 ; следователно показалецът се измества нагоре, както е показано по-долу:

Отново сравняваме стойността 2 с горния ред, т.е. i = 1. Тъй като редът i =0 не съдържа стойност 2, така че ред i = 1 ще бъде избран и теглото, съответстващо на i = 1, е показано 3 По-долу:

X = {1, 1, 0, 0}

Печалбата, съответстваща на теглото, е 2. Следователно оставащата печалба е 0. Сравняваме стойността 0 с горния ред. Тъй като горният ред съдържа стойност 0, но печалбата, съответстваща на този ред, е 0. В този проблем са избрани две тегла, т.е. 3 и 4, за да се увеличи максимално печалбата.