Що таке безмежний рюкзак?

Проблема необмеженого рюкзака заснована на динамічному програмуванні розширення базової задачі про рюкзак 0-1. Ви можете дізнатися більше про проблему ранця 0-1 тут. Єдина відмінність між ранцем 0/1 і необмеженим рюкзаком полягає в тому, що в цьому випадку ми можемо використовувати нескінченну кількість предметів. 26 березня 2024 р.

Повертаючись до динамічного програмування необмеженого рюкзака, єдина різниця між рюкзаком 0/1 (він же обмежений рюкзак) і необмеженим рюкзаком полягає в тому, що немає обмежень щодо вибору кількох екземплярів однієї категорії елементів.

Підхід до динамічного програмування. Цілі оптимізації протилежні: задача необмеженого рюкзака спрямована на максимізувати цінність предметів, тоді як проблема розміну монет спрямована на мінімізацію кількості монет.

Є три типи проблем з рюкзаком: 0-1 рюкзак, Дробовий ранець і Unbounded Knapsack.

Враховуючи вагу та вартість n предметів, завдання полягає в тому, щоб покласти ці предмети в рюкзак місткістю W, щоб отримати максимальну загальну вартість у рюкзаку, ми можемо неодноразово класти той самий предмет, а також можемо покласти частину предмета.

Необмежене означає речі, які не обмежені. У математиці, як правило, речі, які не обмежені, є нескінченними. Ви читали, що обмежені множини повинні мати як верхню, так і нижню межі, але, навпаки, необмежені множини не матимуть верхньої чи нижньої межі.