Завдання про рюкзак алгоритм, рішення - Програмування на C, C# та Java

Уроки програмування, алгоритми, статті, вихідники, приклади програм та корисні поради

Завдання про рюкзак: алгоритм, рішення

Завдання про рюкзак - це одне з найпопулярніших завдань комбінаторної оптимізації. У цій статті розглянемо її формулювання та виконаємо рішення одним із методів за допомогою мови програмування C#.

Формулювання задачі про рюкзак

Наведемо класичне формулюваннязавдання про рюкзак (завдання про ранець).

Умови: Є рюкзак з обмеженою місткістю по масі; також є набір речей з певною вагою та цінністю. Необхідно підібрати такий набір речей, щоб він містився в рюкзаку та мав максимальну цінність (вартість).

Алгоритм розв'язання задачі про рюкзак

Розглянемо один із найпростіших способівточного рішення задачі про рюкзак: це спосібповного перебору.

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

Кожен предмет має: назву, вагу та вартість (цінність):

Щоб вирішити завдання, необхідно скласти всі комбінації наборів предметів і вибрати той набір, маса якого не більше W, а загальна вартість (стосовно інших відповідних наборів) максимальна.

В рамках термінів комбінаторики це означає, що потрібно розглянути всі перестановки з N. Загальна кількість перестановок знаходиться за такою формулою: N!

Якщо предметів п'ять, то доведеться розглянути 5! = 120 різних наборів предметів.

Очевидно, що обчислювальна складність алгоритму повного перебору для вирішеннязавдання про рюкзак дорівнює O(N!).

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

Програма, що вирішує завдання про рюкзак

Перейдемо до написання коду мовою програмування C#.

Опис сутності

Спочатку створимо клас Item, який реалізує сутність "Предмет". Він містить три поля: назву, вагу та вартість.

---