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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

• Вес i- ^го предмета $w_ {i}> 0$

• Прибыль за i- ^й товар $p_ {i}> 0$ и

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

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

Вес i- ^го предмета $w_ {i}> 0$

Прибыль за i- ^й товар $p_ {i}> 0$ и

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

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

$$0 \ leqslant x_ {i} \ leqslant 1$$

I- ^й элемент добавляет вес $x_ {i} .w_ {i}$ к общему весу в рюкзаке, а прибыль $x_ {i} .p_ {i}$ — к общей прибыли.

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

maximize displaystyle sum limitnn=1(xi.pi) $$maximize \: \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .p _ {} i)$$

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

 displaystyle sum limitnn=1(xi.wi) leqslantW $$\ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W$$

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

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

 displaystyle sum limitnn=1(xi.wi)=W $$\ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) = W$$

В этом контексте сначала нам нужно отсортировать эти элементы по значению $\ frac {p_ {i}} {w_ {i}}$, так что $\ frac {p_ {i} +1} {w_ {i } +1}$ ≤ $\ frac {p_ {i}} {w_ {i}}$. Здесь 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 {\ frac {p_ {i}} {w_ {i}}}$, тогда цикл while занимает время в O (n) ; Следовательно, общее время, включая сортировку, составляет O (n logn) .

пример

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

Поскольку предоставленные элементы не отсортированы на основе $\ mathbf {\ frac {p_ {i}} {w_ {i}}}$. После сортировки элементы отображаются так, как показано в следующей таблице.

Решение

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

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

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

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

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

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