Тут рюкзак схожий на контейнер або сумку. Припустимо, ми надали деякі предмети, які мають певну вагу або прибуток. Ми повинні покласти деякі предмети в рюкзак таким чином, щоб загальна вартість приносила максимальний прибуток.
Наприклад, вага контейнера 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 шт
Зазначену вище проблему можна вирішити за допомогою наступного методу:
хi= {1, 0, 0, 1}
= {0, 0, 0, 1}
робити в java
= {0, 1, 0, 1}
Вище наведено можливі комбінації. 1 означає, що елемент вибрано повністю, а 0 означає, що жоден елемент не вибрано. Оскільки є 4 елементи, можливі комбінації будуть:
24= 16; Так. Існує 16 можливих комбінацій, які можна створити, використовуючи наведену вище задачу. Коли всі комбінації складені, ми повинні вибрати комбінацію, яка забезпечує максимальний прибуток.
Іншим підходом до вирішення проблеми є підхід динамічного програмування. У підході динамічного програмування складну задачу поділяють на підпроблеми, потім ми знаходимо розв’язок підпроблеми, а розв’язок підпроблеми буде використано для пошуку розв’язку складної проблеми.
Як цю проблему можна вирішити за допомогою підходу динамічного програмування?
Перший,
ми створюємо матрицю, як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | |||||||||
| 1 | |||||||||
| 2 | |||||||||
| 3 | |||||||||
| 4 |
У наведеній вище матриці стовпці представляють вагу, тобто 8. Рядки представляють прибутки та ваги позицій. Тут ми не взяли вагу 8 безпосередньо, проблема розділена на підпроблеми, тобто 0, 1, 2, 3, 4, 5, 6, 7, 8. Рішення підзадач буде збережено в і відповідь на проблему буде збережено в останній клітинці. Спочатку ми записуємо ваги в порядку зростання, а прибутки відповідно до їх ваг, як показано нижче:
вi= {3, 4, 5, 6}
сторi= {2, 3, 4, 1}
Перший рядок і перший стовпець будуть 0, оскільки немає елемента для w=0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | ||||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i=1, W=1
в1= 3; Оскільки ми маємо лише один предмет у наборі, який має вагу 3, але місткість рюкзака дорівнює 1. Ми не можемо заповнити предмет вагою 3 кг у рюкзак вагою 1 кг, тому додайте 0 до M[1][1], як показано нижче. :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | |||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i = 1, W = 2
в1= 3; Оскільки ми маємо лише один предмет у наборі, який має вагу 3, але місткість рюкзака дорівнює 2. Ми не можемо заповнити предмет вагою 3 кг у рюкзак вагою 2 кг, тому додайте 0 до M[1][2], як показано нижче. :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | ||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i=1, W=3
в1= 3; Оскільки в наборі є тільки один предмет, маса якого дорівнює 3, то і вага рюкзака також дорівнює 3; отже, ми можемо наповнити рюкзак предметом, вага якого дорівнює 3. Ми розміщуємо прибуток, що відповідає вазі 3, тобто 2, у M[1][3], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | |||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i=1, W=4
W1= 3; Оскільки в наборі є лише один предмет, маса якого дорівнює 3, а маса рюкзака дорівнює 4; отже, ми можемо наповнити рюкзак предметом, вага якого дорівнює 3. Ми розміщуємо прибуток, що відповідає вазі 3, тобто 2, у M[1][4], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | ||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i=1, W=5
W1= 3; Так як у наборі є тільки один предмет, маса якого дорівнює 3, а маса рюкзака дорівнює 5; отже, ми можемо наповнити рюкзак предметом, вага якого дорівнює 3. Ми розміщуємо прибуток, що відповідає вазі 3, тобто 2, у M[1][5], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | |||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i =1, W=6
W1= 3; Оскільки в наборі є тільки один предмет, маса якого дорівнює 3, а маса рюкзака дорівнює 6; отже, ми можемо наповнити рюкзак предметом, вага якого дорівнює 3. Ми розміщуємо прибуток, що відповідає вазі 3, тобто 2, у M[1][6], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | ||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i=1, W=7
W1= 3; Оскільки в наборі є тільки один предмет, маса якого дорівнює 3, а маса рюкзака дорівнює 7; отже, ми можемо наповнити рюкзак предметом, вага якого дорівнює 3. Ми розміщуємо прибуток, що відповідає вазі 3, тобто 2, у M[1][7], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | |
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i =1, W =8
W1= 3; Оскільки в наборі є тільки один предмет, маса якого дорівнює 3, а маса рюкзака дорівнює 8; отже, ми можемо наповнити рюкзак предметом, вага якого дорівнює 3. Ми розміщуємо прибуток, що відповідає вазі 3, тобто 2, у M[1][8], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Тепер значення «i» збільшується і стає 2.
Коли i =2, W = 1
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо лише один предмет у наборі, вага якого дорівнює 4, а вага рюкзака дорівнює 1. Ми не можемо помістити предмет маси 4 у рюкзак, тому ми додаємо 0 до M[2][1 ] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | |||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i =2, W = 2
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо лише один предмет у наборі, вага якого дорівнює 4, а вага рюкзака дорівнює 2. Ми не можемо помістити предмет маси 4 у рюкзак, тому ми додаємо 0 до M[2][2]. ] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | ||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i =2, W = 3
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо два предмети в наборі з вагою 3 і 4, а вага рюкзака дорівнює 3. Ми можемо помістити предмет з вагою 3 у рюкзак, тому ми додаємо 2 до M[2][3] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | |||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i =2, W = 4
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки в наборі є два предмети з вагою 3 і 4, а вага рюкзака дорівнює 4. Ми можемо покласти предмет з вагою 4 у рюкзак, оскільки прибуток, що відповідає вазі 4, більший, ніж предмет із вагою 3, тому ми додаємо 3 до M[2][4], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | ||||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i = 2, W = 5
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо два предмети в наборі з вагою 3 і 4, а вага рюкзака дорівнює 5. Ми можемо покласти предмет вагою 4 у рюкзак і прибуток, що відповідає вазі, дорівнює 3, тому ми додаємо 3 до M[2][5] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | |||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i = 2, W = 6
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо два предмети в наборі з вагою 3 і 4, а вага рюкзака дорівнює 6. Ми можемо покласти предмет вагою 4 у рюкзак і прибуток, що відповідає вазі, дорівнює 3, тому ми додаємо 3 до M[2][6] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | ||
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i = 2, W = 7
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо два предмети в наборі з вагою 3 і 4, а вага рюкзака дорівнює 7. Ми можемо покласти предмет з вагою 4 і 3 в рюкзак, і прибутки, що відповідають вагам, дорівнюють 2 і 3; тому загальний прибуток дорівнює 5, тому ми додаємо 5 до M[2][7], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 5 | |
| 3 | 0 | ||||||||
| 4 | 0 |
Коли i = 2, W = 8
Вага, що відповідає значенню 2, дорівнює 4, тобто вага2= 4. Оскільки ми маємо два предмети в наборі з вагою 3 і 4, а вага рюкзака дорівнює 7. Ми можемо покласти предмет з вагою 4 і 3 в рюкзак, і прибутки, що відповідають вагам, дорівнюють 2 і 3; тому загальний прибуток дорівнює 5, тому ми додаємо 5 до M[2][7], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | ||||||||
| 4 | 0 |
Тепер значення «i» збільшується і стає 3.
Коли i = 3, W = 1
concat рядок Java
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки у нас є три предмети в наборі з вагою 3, 4 і 5, а вага рюкзака дорівнює 1. Ми не можемо покласти жоден із предметів у рюкзак, тому ми додаємо 0 до M[3][ 1] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | |||||||
| 4 | 0 |
Коли i = 3, W = 2
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі з вагою 3, 4 і 5, а вага рюкзака дорівнює 1. Ми не можемо покласти жоден із предметів у рюкзак, тому ми додаємо 0 до M[3][ 2] показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | ||||||
| 4 | 0 |
Коли i = 3, W = 3
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі вагою 3, 4 і 5 відповідно, а вага рюкзака дорівнює 3. Предмет із вагою 3 можна покласти в рюкзак, а прибуток, що відповідає цьому предмету, дорівнює 2, тому ми додаємо 2 до M[3][3], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | |||||
| 4 | 0 |
Коли i = 3, W = 4
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі вагою 3, 4 і 5 відповідно, а вага рюкзака дорівнює 4. Ми можемо залишити предмет вагою 3 або 4; прибуток (3), що відповідає вазі 4, більший, ніж прибуток, що відповідає вазі 3, тому ми додаємо 3 до M[3][4], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | ||||
| 4 | 0 |
Коли i = 3, W = 5
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі вагою 3, 4 і 5 відповідно, а вага рюкзака дорівнює 5. Ми можемо залишити предмет вагою 3, 4 або 5; прибуток (3), що відповідає вазі 4, більший, ніж прибуток, що відповідає вазі 3 і 5, тому ми додаємо 3 до M[3][5], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | |||
| 4 | 0 |
Коли i =3, W = 6
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі вагою 3, 4 і 5 відповідно, а вага рюкзака дорівнює 6. Ми можемо залишити предмет вагою 3, 4 або 5; прибуток (3), що відповідає вазі 4, більший, ніж прибуток, що відповідає вазі 3 і 5, тому ми додаємо 3 у M[3][6], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | ||
| 4 | 0 |
Коли i =3, W = 7
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі вагою 3, 4 і 5 відповідно, а вага рюкзака дорівнює 7. У цьому випадку ми можемо залишити обидва предмети маси 3 і 4, сума прибутку буде дорівнювати (2 + 3), тобто 5, тому ми додаємо 5 до M[3][7], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | |
| 4 | 0 |
Коли i = 3, W = 8
Вага, що відповідає значенню 3, дорівнює 5, тобто ват3= 5. Оскільки ми маємо три предмети в наборі вагою 3, 4 і 5 відповідно, а вага рюкзака дорівнює 8. У цьому випадку ми можемо залишити обидва предмети маси 3 і 4, сума прибуток дорівнює (2 + 3), тобто 5, тому ми додаємо 5 до M[3][8], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 |
Тепер значення «i» збільшується і стає 4.
Коли i = 4, W = 1
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 1. Вага всіх предметів більша за вагу рюкзака, тому ми не можемо додати будь-який предмет в рюкзак; Тому ми додаємо 0 до M[4][1], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 |
Коли i = 4, W = 2
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 2. Вага всіх предметів більша за вагу рюкзака, тому ми не можемо додати будь-який предмет в рюкзак; Тому ми додаємо 0 до M[4][2], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 |
Коли i = 4, W = 3
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 3. Предмет із вагою 3 можна покласти в рюкзак і отримати прибуток, відповідний вага 4 дорівнює 2, тому ми додамо 2 до M[4][3], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 |
Коли i = 4, W = 4
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 4. Предмет із вагою 4 можна покласти в рюкзак і отримати прибуток, відповідний вага 4 дорівнює 3, тому ми додамо 3 до M[4][4], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 |
Коли i = 4, W = 5
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 5. Предмет із вагою 4 можна покласти в рюкзак і отримати прибуток, відповідний вага 4 дорівнює 3, тому ми додамо 3 до M[4][5], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 |
Коли i = 4, W = 6
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 6. У цьому випадку ми можемо покласти в рюкзак предмети з вагою 3, 4 , 5 або 6, але прибуток, тобто 4, що відповідає вазі 6, є найвищим серед усіх позицій; тому ми додаємо 4 до M[4][6], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 |
Коли i = 4, W = 7
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 7. Тут, якщо ми додамо два предмети вагою 3 і 4, це дасть максимальну прибуток, тобто (2 + 3) дорівнює 5, тому ми додаємо 5 до M[4][7], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 |
Коли i = 4, W = 8
Вага, що відповідає значенню 4, дорівнює 6, тобто ват4= 6. Оскільки ми маємо чотири предмети в наборі вагою 3, 4, 5 і 6 відповідно, а вага рюкзака дорівнює 8. Тут, якщо ми додамо два предмети вагою 3 і 4, це дасть максимум прибуток, тобто (2 + 3) дорівнює 5, тому ми додаємо 5 до M[4][8], як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
Як ми бачимо в наведеній вище таблиці, 5 — це максимальний прибуток серед усіх записів. Покажчик вказує на останній рядок і останній стовпець із значенням 5. Тепер ми порівняємо значення 5 з попереднім рядком; якщо попередній рядок, тобто i = 3, містить те саме значення 5, то вказівник зміститься вгору. Оскільки попередній рядок містить значення 5, вказівник буде зміщено вгору, як показано в таблиці нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
Знову ми порівняємо значення 5 із наведеного вище рядка, тобто i = 2. Оскільки наведений вище рядок містить значення 5, вказівник знову буде зміщено вгору, як показано в таблиці нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
Знову ж таки, ми порівняємо значення 5 із наведеного вище рядка, тобто i = 1. Оскільки вищезгаданий рядок не містить такого самого значення, ми розглянемо рядок i=1, а вага, що відповідає рядку, дорівнює 4. Тому , ми вибрали вагу 4 і відхилили ваги 5 і 6, показані нижче:
x = { 1, 0, 0}
mylivericket
Прибуток, що відповідає вазі, дорівнює 3. Отже, решта прибутку (5 - 3) дорівнює 2. Тепер ми порівняємо це значення 2 із рядком i = 2. Оскільки рядок (i = 1) містить значення 2 ; тому покажчик змістився вгору, як показано нижче:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
Знову ми порівнюємо значення 2 із наведеним вище рядком, тобто i = 1. Оскільки рядок i = 0 не містить значення 2, буде вибрано рядок i = 1, а вага, що відповідає i = 1, буде показана 3. нижче:
X = {1, 1, 0, 0}
Прибуток, що відповідає вазі, дорівнює 2. Таким чином, решта прибутку дорівнює 0. Ми порівнюємо значення 0 із наведеним вище рядком. Оскільки наведений вище рядок містить значення 0, але прибуток, що відповідає цьому рядку, дорівнює 0. У цій задачі вибрано дві ваги, тобто 3 і 4, щоб максимізувати прибуток.