0/1 с весом зависимого веса?

Стандартный ранец 0/1 требует, чтобы вес каждого предмета был независим от других. Тогда DP - эффективный алгоритм решения. Но теперь я встретил аналогичные, но расширяет эту проблему, что

вес новых элементов зависит от предыдущих элементов, уже находящихся в рюкзак.

Например, у нас есть 5 элементов a, b, c, d и e с весом w_a,..., w_e. item b и c имеют зависимость от веса.

Когда b уже находится в рюкзаке, вес элемента c будет меньше, чем w_c, потому что он может совместно использовать некоторое пространство с b, т.е. weight(b&c) < w_b + w_c. Симметрично, когда c уже находится в рюкзаке, вес b будет меньше, чем w_b.

Эта неопределенность приводит к сбою оригинального алгоритма DP, поскольку он зависит от правильности предыдущих итераций, которые могут не исправить сейчас. Я прочитал несколько статей о рюкзаке, но у них либо есть зависимости, подверженные прибыли (квадратичная проблема с рюкзаком), либо переменная масса, которая следует за случайным распределением (проблема стохастического ранца). Я также знал о предыдущем вопросе 1/0 Вариант рюкзака с взвешенными краями, но есть только очень общий ответ, и нет ответа о том, что называется именем этот рюкзак.

Одно существующее решение:

Я также прочитал одно приблизительное решение в статью об оптимизации СУБД, где они group the related items as one combined item for knapsack. Если использовать этот метод в нашем примере, элементы для ранца будут a, bc, d, e, поэтому нет никаких зависимостей между любыми двумя из этих четырех элементов. Однако легко построить пример, который не получает оптимального результата, например, при an item with "small weight and benefit" is grouped with another item with "large weight and benefit". В этом примере "маленький" элемент не должен выбираться в решении, но выбран вместе с "большим" элементом.

Вопрос:

Есть ли какие-либо эффективные методы решения, которые могут получить оптимальный результат или, по крайней мере, с некоторой ошибкой? Или я беру неправильное направление для моделирования этой проблемы?

Ответ 1

В конце концов мне удалось решить проблему с помощью метода B & B, предложенного @Holt. Вот основные настройки:

(0) Перед запуском алгоритма B & B группа всех элементов зависит от их зависимости. Все элементы в одном разделе имеют зависимость от веса со всеми другими элементами в той же группе, но не с элементами в других группах.

Настройки для B & B:

(1) Верхняя граница: предположим, что текущий элемент имеет вес минимум, т.е. предполагают существование всех зависимостей.

(2) Нижняя граница: предположим, что текущий элемент имеет вес максимум, т.е. предполагается, что все зависимости не существуют.

(3) Текущий вес: Рассчитать реальный текущий вес.

Все приведенные выше вычисления могут выполняться в линейном времени, играя с группами, которые мы получаем на шаге 0. В частности, при получении этих весов просматриваются только те объекты в текущей группе (группа, в которой находится текущий элемент) достаточно - элементы в других группах не имеют зависимости от текущего, поэтому он не изменит реальный вес текущего элемента.

Ответ 2

Не могли бы вы иметь элементы a, b, c, bc, d и e? Возможно, с ограничением, что b и bc не могут быть как в рюкзаке, так и с помощью c и bc? Я понимаю, что это было бы правильным решением, поскольку любое решение, имеющее b и c, может быть улучшено путем подстановки как bc (по определению). Ограничения на членство должны заботиться о любых других случаях.

Ответ 3

Это очень интересная проблема, и я работал над этим некоторое время. Первое, что нужно учитывать, это то, что проблема двоичного рюкзака с зависимыми весами/значением элемента вообще не является тривиальной. Вы можете использовать байесовские сети, марковские модели и другие подобные методы для решения этой проблемы. Тем не менее, любой практический подход к этой проблеме должен сделать некоторые предположения ни о модели оптимизации, ни о ее вводе. Вот пример формулировки проблемы двоичного рюкзака со значениями зависимых элементов. https://arxiv.org/pdf/1702.06662.pdf

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

Пожалуйста, не стесняйтесь обращаться ко мне, если вам нужна дополнительная информация. Я также могу предоставить вам исходный код модели, если это необходимо.