проблема с рюкзаком

проблема с рюкзаком

Задача о рюкзаке — одна из 21 NP-полной задачи Ричарда Карпа, изложенных в его статье 1972 года.

состояния

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

Наиболее распространенной формой является задача о рюкзаке 0-1 (0-1 КП), ограничивающая количество копий xя каждого объекта i максимум в одной копии. Пусть есть набор из n объектов, наделенных весом wя и полезно vя, а вместимостью рюкзака W задача записывается так:

максимизировать ∑я=1нет вя*Икся
при условии ∑я=1нет вя*Икся ≤ W и хя ∈ {0,1}.

Задача об ограниченном рюкзаке (ЗКП) снимает ограничение ограничения объекта ограничением, ограниченным целым числом cя:

максимизировать ∑я=1нет вя*Икся
при условии ∑я=1нет вя*Икся ≤ W и хя ∈ {0,...,ся}.

Задача о неограниченном рюкзаке UKP не накладывает ограничений на количество копий каждого объекта.

максимизировать ∑я=1нет вя*Икся
при условии ∑я=1нет вя*Икся ≤ W и 0≤xя .

проблема с рюкзаком 0-1 рюкзак снижение NP

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

Методы разрешения

Жадный алгоритм

Идея состоит в том, чтобы сначала добавлять наиболее эффективные объекты, пока сумка не заполнится:

 Сортировать объекты в порядке убывания эффективности w_conso := 0

за я из 1 в нет
  если w[i] + w_conso ≤ W тогда
    х[i]:= 1 w_conso:= w_conso + w[i]
  в противном случае
    х[я] := 0
  конец, если
конец для 

Динамическое программирование

Задача о рюкзаке обладает свойством оптимальной подструктуры, т. е. можно построить оптимальное решение задачи с k-переменной из задачи с k-1 переменной.

Пусть Fк(E) наилучшая стоимость заполнения мешка размера E k
первые объекты. Повторение показывает, что Fк(Е) = макс {Fk−1(Э), Фk−1(E−wк)+vк},

действительно добавление нового объекта увеличивает или не лучшую стоимость. В случае, если новый объект не добавлен в корзину, Fк(Е) равно Fk−1(Э). В случае, когда новый предмет предлагает лучшую полезность, т. е. в случае, когда предмета нет, но в сумке (без предмета) достаточно места для размещения нового элемента, и он оптимален (т. е. формула Fk−1(E−wк)), затем Fк(Е) равно Fk−1(E−wк) + vк, vк полезность нового предмета, добавленного в сумку, описанную выше.

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

за против из 0 в Вт Сделать
  Т[0,с] := 0
конец для

за я из 1 в нет Сделать
  за против из 0 в Вт Сделать
    если с>=ш[я] тогда
      T[i,c] := max(T[i-1,c], T[i-1, cw[i]] + p[i])
    в противном случае
      Т[я,с] := Т[я-1,с]
    конец, если
  конец для
конец для 

Имеются следующие элементы: C = 8 и пять объектов, описанных в
таблица ниже

я
1
2
3
4
5
Пи
3
4
5
4
2
у_и
15
18
20
12
6

Получаем следующую таблицу результатов рюкзака:

Е | я
1
2
3
4
5
0
0
0
0
0
0
1
0
0
0
0
0
2
6
6
6
6
6
3
15
6
6
6
6
4
15
18
12
12
6
5
21
20
20
12
6
6
24
24
20
18
6
7
33
26
26
18
6
8
35
30
26
18
6

Оптимальное решение 25 получается с элементами 1 и 3 по второму
алгоритм рюкзака:

к
1
2
3
4
5
Е
8
5
5
0
0
х[к]
1
0
1
0
0

консо = консо_1 + консо_3 = 8.

Делиться
ru_RURU
%d такие блоггеры, как: