Неполиномиальные задачи. Задача о рюкзаке

Имеется N предметов, каждый из которых имеет объём V_i и стоимость C_i, предметы неделимы. Имеется рюкзак вместимостью V. Требуется поместить в рюкзак набор предметов максимальной стоимости, суммарный объём которых не превышает объёма рюкзака.

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

Обратим внимание на то, что предметы разрезать на куски нельзя. Если это разрешить, то задача будет иметь простое решение.

Для решения задачи достаточно перебрать все возможные комбинации из N предметов. Это гарантирует то, что мы не пропустим нужной комбинации.

Для определения количества комбинаций можно рассуждать так, что K предметов можно выбрать из N предметов (C_N^K), и так для всех K от 0 до N.

F(N) = (1 + 1) ^N = 2^N

Одно из решений задачи о рюкзаке

1) перенумеруем все предметы;

2) установим максимум стоимости в 0;

3) составим двоичное число с N разрядами, в котором единица в разряде будет означать, что предмет выбран для укладки в рюкзак (расстановку);

4) рассмотрим все расстановки, начиная от 000 ... 000 до 111 ... 111, для каждой из них подсчитаем значение суммарного объёма:

4.1) если суммарный объём расстановки не превосходит объёма рюкзака, то подсчитывается суммарная стоимость и сравнивается с достигнутым ранее максимумом стоимости;

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

Свойства алгоритма

Предложенный алгоритм:

1) детерминированный;

2) конечный;

3) массовый;

4) полезный.

Его сложность пропорциональна 2^N, так как требуется перебрать все возможные комбинации предметов.

Сложность решения задачи о рюкзаке

Много ли времени потребуется на решение задачи для N = 128?

Предположим, на подсчёт одного решения потребуется 10^-9 секунд, т.е. одна наносекунда.

Предположим, задачу будет решать триллион компьютеров (10¹²).

Тогда общее время решения задачи будет составлять

NP-задачи о рюкзаке

Задача о рюкзаке относится к классу NP-полных. Быстрое (полиномиальное) точное решение таких задач (пока) не найдено. Если будет найдено решение одной из NP-полных задач, то будут решены все задачи из этого класса. Сейчас их решают приближённо.

Исполнитель алгоритма Исполнители

Нашим исполнителем будет язык C++.

Элементарные типы отображаются на вычислительную систему char, int, double.

Элементарные операции аппаратного исполнителя: операции над элементарными типами и операции передачи управления.

Типы данных языка – комбинация элементарных типов данных.

Операции языка – комбинация элементарных операций.

Элементарные и неэлементарные операции

Пример: цикл for – это неэлементарная операции языка.

int a[10];

int s = 0;

for (int i = 0; i < 10 && a[i] % 10 != 5; i++) s += a[i];

Массив – это неэлементарный тип, в данном примере его представитель a.

int – это элементарный тип, в данном примере его представитель s.

Элементарная операция присваивания (инициализации): s = 0.

for – это неэлементарная операция, состоящая из операций присваивания (i = 0), двух операций сравнения, и т. д.