DAA - дробный рюкзак

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

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

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

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

Приложения

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

• Поиск наименее расточительного способа сократить сырье
• оптимизация портфеля
• Проблемы с раскроем

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

Вор грабит магазин и может нести максимальный вес Wв его рюкзак. В магазине n штук, весi^th товар w_i и его прибыль p_i. Какие предметы должен взять вор?

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

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

• Дробный рюкзак
• Knapsack

Дробный рюкзак

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

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

• Есть n товары в магазине

• Вес i^th товар $ w_ {i}> 0 $

• Прибыль за i^th элемент $ p_ {i}> 0 $ и

• Вместимость ранца W

В этой версии задачи о ранце предметы можно разбивать на более мелкие части. Значит, вор может забрать только частьx_i из i^th вещь.

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

В i^th item добавляет вес $ x_ {i} .w_ {i} $ к общему весу в рюкзаке и прибыль $ x_ {i} .p_ {i} $ к общей прибыли.

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

$$ развернуть \: \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

при условии ограничения,

$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

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

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

$$ \ displaystyle \ sum \ limits_ {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 и список предоставленных предметов показан в следующей таблице -

Вещь	А	B	C	D
Прибыль	280	100	120	120
Вес	40	10	20	24
Соотношение $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

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

Вещь	B	А	C	D
Прибыль	100	280	120	120
Вес	10	40	20	24
Соотношение $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Решение

После сортировки всех элементов в соответствии с $ \ 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

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