Задача о рюкзаке

Задача о рюкзаке – это одна из самых популярных задач комбинаторной оптимизации. В этой статье рассмотрим её формулировку и выполним решение одним из методов с помощью языка программирования C#.

Формулировка задачи о рюкзаке

Приведём классическую формулировку задачи о рюкзаке (задачи о ранце).

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

Задача о рюкзаке (задача о ранце)

Алгоритм решения задачи о рюкзаке

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

Обозначим максимальный вес ранца, как W, а количество различных вещей N. При этом в наборе могут быть абсолютно одинаковые предметы.

Каждый предмет имеет: название, вес и стоимость (ценность):

 Название  Вес  Стоимость
 Книга  1  600
 Бинокль  2  5000
 Аптечка  4  1500
 Ноутбук  2  40000
 Котелок  1  500

Чтобы решить задачу, необходимо составить все комбинации наборов предметов и выбрать тот набор, масса которого не более W, а общая стоимость (по отношению к другим подходящим наборам) максимальна.

В рамках терминов комбинаторики это означает, что нужно рассмотреть все перестановки из N. Общее количество перестановок находится по формуле: N!

Если предметов пять, то придётся рассмотреть 5! = 120 различных наборов предметов.

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

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

Программа, решающая задачу о рюкзаке

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

Описание сущности

Сначала создадим класс Item, который реализует сущность “Предмет”. Он содержит три поля: название, вес и стоимость.

Класс, решающий задачу о ранце

Далее закодируем класс Backpack (рюкзак), который составляет и перебирает все наборы предметов и выбирает из них самый лучший (его общая масса не больше W, а стоимость среди подходящих по массе наборов – максимальна). Поля и конструктор класса:

В полях хранится: лучший набор предметов для рюкзака, максимальная масса рюкзака и общая стоимость предметов лучшего набора bestItems соответственно.

Далее методы, которые по списку предметов List<Item> вычисляют их суммарный вес и стоимость:

Затем метод, сравнивающий текущий лучший набор предметов (список List) в экземпляре класса с набором предметов из аргументов метода. Если набор из аргументов лучше, то он сохраняется в поле класса:

Теперь самый главный метод класса. Он перебирает все возможные наборы (перестановки) предметов для рюкзака. Данный метод рекурсивный. Сначала в наборе все N предметов, затем, при переходе вглубь на один уровень рекурсии, один предмет удаляется. Выход из рекурсии произойдёт, когда список предметов станет пустым. Код метода:

Последний метод в классе Backpack возвращает набор предметов, являющийся решением задачи:

Создание интерфейса программы и его функциональности

Расположим на форме Windows Forms элемент управления ListView с тремя столбцами под атрибуты сущности “Предмет” – в него будем выводить исходный набор данных, а затем решение задачи. Потом добавим Label с надписью “Максимальный вес рюкзака”, далее TextBox (в котором записан этот максимальный вес) и две кнопки (Button) – “Решить” и “Показать исходные данные” (будет выводить набор предметов из условия в ListView).

Интерфейс программы для решения задачи о рюкзаке

Перейдём к коду класса Form1. Класс содержит единственное поле:

В нём будет хранится список предметов, которыми необходимо заполнить ранец, чтобы его стоимость была максимальна.

Исходные данные мы заполним прямо в коде:

Вы же можете реализовать ввод данных из файла, либо сделать его прямо в окне графического интерфейса программы; как будет необходимо.

Затем идёт метод, который выводит список предметов в ListView:

Соответственно конструктор класса выглядит следующим образом:

То есть список List заполняется исходными данными о предметах для рюкзака и выводится на экран.

Теперь код кнопки “Показать исходные данные”:

И код кнопки “Решить”:

Если решения нет, то будет выведен соответствующий MessageBox с оповещением, если решение есть – оно будет выведено на экран и MessageBox также сообщит об этом.

Написание кода завершено.

Демонстрация работы программы

Итак, решим задачу о рюкзаке с помощью написанной программы. Исходные данные о предметах – из таблицы выше; вместимость ранца – 8 килограмм.

Задача о рюкзаке - Исходные данные

Нажмём кнопку “Решить” и получим решение задачи. Оно приведено в таблице на окне программы:

Задача о рюкзаке - Решение задачи

Скачать исходник программы, либо перейти в репозиторий проекта на GitHub:

Скачать исходник Репозиторий проекта на GitHub

 

 

Надеемся, что данная статья и программа помогли Вам разобраться с решением задачи о рюкзаке на языке C#. Спасибо за прочтение!

Задача о рюкзаке
5 (100%) 7 votes

Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">