Постоянная проблема с рюкзаком

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

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

Пример либо непрерывной, либо классической задачи о рюкзаке может быть определен числовой вместимостью W рюкзака вместе с набором материалов, с каждым из которых связаны два числа: вес w _i материала, доступного для использования. выбранного и общую стоимость v _i этого материала. Цель состоит в том, чтобы выбрать количество x _i ≤ w _i каждого материала с учетом ограничения производительности. $$\sum _{i}x_{i}\leq W$$и максимизировать общую выгоду $$\sum _{i}x_{i}v_{i}.$$В классической задаче о рюкзаке каждая из величин x _i должна быть либо нулем, либо w _i ; Задача о непрерывном рюкзаке отличается тем, что позволяет изменяться _{непрерывно} от нуля до wi _xi .

В некоторых формулировках этой задачи переменные x _i масштабируются в диапазоне от 0 до 1. В этом случае ограничение пропускной способности принимает вид $$\sum _{i}x_{i}w_{i}\leq W,$$и цель состоит в том, чтобы максимизировать общую выгоду $$\sum _{i}x_{i}v_{i}.$$

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

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

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

Из-за необходимости сортировки материалов этот алгоритм требует времени O ( n log n ) на входных данных с n материалами. Однако, адаптировав алгоритм нахождения взвешенных медиан , можно решить задачу за время O ( n ).