Задача о рюкзаке: алгоритм, решение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BackpackTask
{
    class Item
    {
        public string name { get; set; }

        public double weigth { get; set; }

        public double price { get; set; }

        public Item(string _name, double _weigth, double _price)
        {
            name = _name;
            weigth = _weigth;
            price = _price;
        }

    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace BackpackTask

{

class Item

{

public string name { get; set; }

public double weigth { get; set; }

public double price { get; set; }

public Item(string _name, double _weigth, double _price)

{

name = _name;

weigth = _weigth;

price = _price;

}

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

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

private List<Item> bestItems = null;

private double maxW;

private double bestPrice;

public Backpack(double _maxW)
{
    maxW = _maxW;
}

private List<Item> bestItems = null;

private double maxW;

private double bestPrice;

public Backpack(double _maxW)

{

maxW = _maxW;

}

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

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

//вычисляет общий вес набора предметов
private double CalcWeigth(List<Item> items)
{
    double sumW = 0;

    foreach(Item i in items)
    {
        sumW += i.weigth;
    }

    return sumW;
}

//вычисляет общую стоимость набора предметов
private double CalcPrice(List<Item> items)
{
    double sumPrice = 0;

    foreach (Item i in items)
    {
        sumPrice += i.price;
    }

    return sumPrice;
}

//вычисляет общий вес набора предметов

private double CalcWeigth(List<Item> items)

{

double sumW = 0;

foreach(Item i in items)

{

sumW += i.weigth;

}

return sumW;

}

//вычисляет общую стоимость набора предметов

private double CalcPrice(List<Item> items)

{

double sumPrice = 0;

foreach (Item i in items)

{

sumPrice += i.price;

}

return sumPrice;

}

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

//проверка, является ли данный набор лучшим решением задачи
private void CheckSet(List<Item> items)
{
    if (bestItems == null)
    {
        if (CalcWeigth(items) <= maxW)
        {
            bestItems = items;
            bestPrice = CalcPrice(items);
        }
    }
    else
    {
        if(CalcWeigth(items) <= maxW && CalcPrice(items) > bestPrice)
        {
            bestItems = items;
            bestPrice = CalcPrice(items);
        }
    }
}

//проверка, является ли данный набор лучшим решением задачи

private void CheckSet(List<Item> items)

{

if (bestItems == null)

{

if (CalcWeigth(items) <= maxW)

{

bestItems = items;

bestPrice = CalcPrice(items);

}

else

{

if(CalcWeigth(items) <= maxW && CalcPrice(items) > bestPrice)

{

bestItems = items;

bestPrice = CalcPrice(items);

}

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

//создание всех наборов перестановок значений
public void MakeAllSets(List<Item> items)
{
    if (items.Count > 0)
        CheckSet(items);

    for (int i = 0; i < items.Count; i++)
    {
        List<Item> newSet = new List<Item>(items);

        newSet.RemoveAt(i);

        MakeAllSets(newSet);
    }

}

//создание всех наборов перестановок значений

public void MakeAllSets(List<Item> items)

{

if (items.Count > 0)

CheckSet(items);

for (int i = 0; i < items.Count; i++)

{

List<Item> newSet = new List<Item>(items);

newSet.RemoveAt(i);

MakeAllSets(newSet);

}

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

//возвращает решение задачи (набор предметов)
public List<Item> GetBestSet()
{
    return bestItems;
}

//возвращает решение задачи (набор предметов)

public List<Item> GetBestSet()

{

return bestItems;

}

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

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

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

private List<Item> items;

1	private List<Item> items;

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

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

private void AddItems()
{
    items = new List<Item>();

    items.Add(new Item("Книга", 1, 600));
    items.Add(new Item("Бинокль", 2, 5000));
    items.Add(new Item("Аптечка", 4, 1500));
    items.Add(new Item("Ноутбук", 2, 40000));
    items.Add(new Item("Котелок", 1, 500));
}

private void AddItems()

{

items = new List<Item>();

items.Add(new Item("Книга", 1, 600));

items.Add(new Item("Бинокль", 2, 5000));

items.Add(new Item("Аптечка", 4, 1500));

items.Add(new Item("Ноутбук", 2, 40000));

items.Add(new Item("Котелок", 1, 500));

}

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

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

private void ShowItems(List<Item> _items)
{
    itemsListView.Items.Clear();

    foreach (Item i in _items)
    {
        itemsListView.Items.Add(new ListViewItem(new string[] { i.name, i.weigth.ToString(), 
            i.price.ToString() }));
    }
}

private void ShowItems(List<Item> _items)

{

itemsListView.Items.Clear();

foreach (Item i in _items)

{

itemsListView.Items.Add(new ListViewItem(new string[] { i.name, i.weigth.ToString(),

i.price.ToString() }));

}

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

public Form1()
{
    InitializeComponent();

    AddItems();
    ShowItems(items);
}

public Form1()

{

InitializeComponent();

AddItems();

ShowItems(items);

}

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

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

private void ShowConditionsButton_Click(object sender, EventArgs e)
{
    ShowItems(items);
}

private void ShowConditionsButton_Click(object sender, EventArgs e)

{

ShowItems(items);

}

И код кнопки «Решить»:

private void solveButton_Click(object sender, EventArgs e)
{
    Backpack bp = new Backpack(Convert.ToDouble(weightTextBox.Text));

    bp.MakeAllSets(items);

    List<Item> solve = bp.GetBestSet();

    if(solve == null)
    {
        MessageBox.Show("Нет решения!");
    }
    else
    {
        itemsListView.Items.Clear();

        ShowItems(solve);

        MessageBox.Show("Решение приведено в таблице");
    }
}

private void solveButton_Click(object sender, EventArgs e)

{

Backpack bp = new Backpack(Convert.ToDouble(weightTextBox.Text));

bp.MakeAllSets(items);

List<Item> solve = bp.GetBestSet();

if(solve == null)

{

MessageBox.Show("Нет решения!");

}

else

{

itemsListView.Items.Clear();

ShowItems(solve);

MessageBox.Show("Решение приведено в таблице");

}

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

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

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

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

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

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

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

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

4.6/5 - (24 голоса)

c#, Алгоритм, Задача, Задача о ранце, Задача о рюкзаке

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

3 комментария(ев) к статье “Задача о рюкзаке: алгоритм, решение”

Олег 01.06.2017 в 09:53

Подскажите, пожалуйста, какие изменения нужно внести, чтобы выполнялось еще одно условие — брать в рюкзак можно только определенное количество предметов?

Ответить
Михаил 31.05.2019 в 14:25

Программа работает. Переписал ее себе на Java, пытаюсь понять и не могу — в методе MakeAllSets мы перебираем варианты, отбрасывая первый (нулевой) элемент набора, и в какой-то момент набор newSet становится пустым, в цикле по i мы казалось бы должны бы были зависнуть, т.к. items.size() == 0; но каким-то непонятным мне образом i увеличивается на единицу и появляется непустой newSet. Как? откуда? Я тупой..

Ответить
1. admin Автор статьи01.06.2019 в 15:00
  
  Обратите внимание — данный метод рекурсивный, возможно, вы это упустили. При items.Count == 0 никаких зависаний происходить не может. Когда items.Count равно нулю, происходит выход из метода (просто потому что никаких действий не будет произведено — ни условие if ни цикл выполняться не будут) и переход на уровень выше по рекурсии.
  
  Ответить

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы