Учебники

DAA – Фракционный рюкзак

Алгоритм Жадности может быть очень хорошо понят с хорошо известной проблемой, называемой проблемой ранца. Хотя та же проблема может быть решена путем использования других алгоритмических подходов, подход Greedy позволяет решить проблему дробного ранца в разумные сроки. Остановимся подробнее на проблеме рюкзака.

Рюкзак Проблема

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

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

Приложения

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

  • Нахождение наименее расточительного способа резки сырья
  • оптимизация портфеля
  • Проблемы с заготовкой

Сценарий проблемы

Вор грабит магазин и может нести максимальный вес W в свой рюкзак. В магазине доступно n предметов, и вес i- го предмета равен w i, а его прибыль равна p i . Какие вещи должен взять вор?

В этом контексте предметы должны быть выбраны таким образом, что вор будет нести те предметы, за которые он получит максимальную прибыль. Следовательно, цель вора – максимизировать прибыль.

В зависимости от характера предметов проблемы с рюкзаком подразделяются на

  • Фракционный рюкзак
  • ранец

Фракционный рюкзак

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

Согласно постановке задачи,

  • В магазине n товаров

  • Вес i- го предмета wi>0

  • Прибыль за i- й товар pi>0 и

  • Емкость Рюкзака Вт

В магазине n товаров

Вес i- го предмета wi>0

Прибыль за i- й товар pi>0 и

Емкость Рюкзака Вт

В этой версии задачи о ранце предметы могут быть разбиты на более мелкие части. Таким образом, вор может взять только часть x i из i- го предмета.

0 leqslantxi leqslant1

I- й элемент добавляет вес xi.wi к общему весу в рюкзаке, а прибыль xi.pi – к общей прибыли.

Следовательно, целью этого алгоритма является

maximize displaystyle sum limitnn=1(xi.pi)

с учетом ограничений,

 displaystyle sum limitnn=1(xi.wi) leqslantW

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

Таким образом, оптимальное решение может быть получено

 displaystyle sum limitnn=1(xi.wi)=W

В этом контексте сначала нам нужно отсортировать эти элементы по значению  fracpiwi, так что  fracpi+1wi+1 fracpiwi. Здесь x – массив для хранения доли элементов.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Анализ

Если предоставленные элементы уже отсортированы в порядке убывания  mathbf fracpiwi, тогда цикл while занимает время в O (n) ; Следовательно, общее время, включая сортировку, составляет O (n logn) .

пример

Предположим, что вместимость ранца W = 60 и список предоставленных предметов показаны в следующей таблице:

Вещь В С D
прибыль 280 100 120 120
Вес 40 10 20 24
Соотношение ( fracpiwi) 7 10 6 5

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

Вещь В С D
прибыль 100 280 120 120
Вес 10 40 20 24
Соотношение ( fracpiwi) 10 7 6 5

Решение

После сортировки всех элементов по  fracpiwi. Сначала выбирается все B, так как вес B меньше вместимости рюкзака. Затем выбирается элемент A , так как доступная вместимость рюкзака больше, чем вес A. Теперь C выбран в качестве следующего элемента. Тем не менее, весь предмет не может быть выбран, так как оставшийся объем рюкзака меньше, чем вес C.

Следовательно, доля C (то есть (60 – 50) / 20) выбрана.

Теперь вместимость рюкзака равна выбранным предметам. Следовательно, больше ничего нельзя выбрать.

Общий вес выбранных предметов составляет 10 + 40 + 20 * (10/20) = 60

И общая прибыль составляет 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Это оптимальное решение. Мы не можем получить больше прибыли, выбирая любую другую комбинацию предметов.