Непрерывная задача о рюкзаке - Continuous knapsack problem

В теоретическая информатика, то непрерывная задача о рюкзаке (также известный как дробная задача о ранце) является алгоритмический проблема в комбинаторная оптимизация в котором цель состоит в том, чтобы заполнить контейнер («рюкзак») дробными количествами различных материалов, выбранных для максимизации ценности выбранных материалов.^[1][2] Походит на классику проблема с рюкзаком, в котором предметы, помещаемые в контейнер, неделимы; однако проблема непрерывного ранца может быть решена в полиномиальное время тогда как классическая задача о рюкзаке NP-жесткий.^[1] Это классический пример того, как, казалось бы, небольшое изменение в формулировке проблемы может иметь большое влияние на ее решение. вычислительная сложность.

Определение проблемы

Пример непрерывной или классической задачи о ранце может быть задан числовой емкостью W рюкзака вместе с набором материалов, с каждым из которых связано два числа: вес ш_я материала, который доступен для выбора, и общая стоимость v_я из этого материала. Цель - выбрать сумму Икс_я ≤ ш_я каждого материала, с учетом ограничений производительности

${displaystyle sum _ {i} x_ {i} leq W}$

и максимизация общей выгоды

${displaystyle sum _ {i} x_ {i} v_ {i}}$.

В классической задаче о рюкзаке каждая из сумм Икс_я должен быть либо нулем, либо ш_я; задача о непрерывном рюкзаке отличается тем, что позволяет Икс_я непрерывно изменяться от нуля до ш_я.^[1]

Некоторые формулировки этой проблемы изменяют масштаб переменных Икс_я быть в диапазоне от 0 до 1. В этом случае ограничение мощности становится

${displaystyle sum _ {i} x_ {i} w_ {i} leq W}$,

и цель - максимизировать общую выгоду

${displaystyle sum _ {i} x_ {i} v_ {i}}$.

Техника решения

Проблему непрерывного ранца можно решить с помощью жадный алгоритм, впервые опубликовано в 1957 г. Джордж Данциг,^[2][3] который рассматривает материалы в отсортированном порядке по их удельному весу. Для каждого материала количество Икс_я выбирается как можно больше:

• Если сумма сделанных до сих пор выборов равна емкости W, то алгоритм устанавливает Икс_я = 0.
• Если разница d между суммой сделанных выборов и W меньше чем ш_я, то алгоритм устанавливает Икс_я = d.
• В оставшемся случае алгоритм выбирает Икс_я = ш_я.

Из-за необходимости сортировки материалов этот алгоритм требует времени. О(п бревноп) на входах с п материалы.^[1][2] Однако, адаптировав алгоритм нахождения взвешенные медианы, возможно вовремя решить проблему О(п).^[2]

Рекомендации