Минимизируйте стоимость доставки на основе ограничений по цене и весу

Question

Я пытаюсь определить наименьшую стоимость доставки, когда у вас есть несколько предметов (каждый с весом и ценой), которые можно объединить в одну упаковку.Ограничения следующие:

1. Существует ограничение на максимальную цену комбинированного пакета (скажем, 15 долларов США)
2. Стоимость пакета определяется с использованием следующей таблицы:
   1. Если общий вес упаковки составляет <30 грамм, стоимость составляет 7,5 $ </li>
   2. Если общий вес упаковки> = 30 г и <80 г, стоимость составляет 7,5 $ + (вес - 30) x0,075 </li>
   3. Если общий вес упаковки составляет> = 80 г, стоимость составляет 7,5 долл. США + (вес - 30) x0,055

Нет ограничений на количествопакеты, в которые эти предметы могут быть объединены, пока они остаются под порогом общей цены.

Я смотрел на проблему с рюкзаком, но есть 2 основных различия между проблемой с рюкзаком и моей проблемой:

1. Во-первых, мы не максимизируем вес или цену объединенных предметов, а хотим минимизировать вычисляемую переменную, которая может быть определена только после комбинации.
2. Кроме того, прямойкорреляция между весом аи стоимость доставки.

Answer 1

Если у вас есть небольшое количество предметов, это можно решить с помощью брутфорса с использованием бинарной маски. Определите n как количество элементов. Когда значение m (0 <= m < 2^n) представляет двоичную маску с длиной, равной n (с начальными нулями, если необходимо). Маска показывает, какие элементы уже обработаны (i бит равен 1 в маске, если i элементы уже обработаны). Определите F[m] минимальную стоимость для подмножества предметов из маски m. Когда F[m] = min(F[m xor x] + cost(x)) для всего значения x, для которого m and x = x (x является подмножеством m). xor и and являются двоичной операцией. cost(x) стоит один пакет с предметами из маски x (после 2. из выписки). Сложность этого алгоритма будет O(4^n) (менее чем за секунду на хорошем компьютере для n <= ~ 14). Но вы можете использовать этот <a href="https://cp-algorithms.com/algebra/all-submasks.html" rel="nofollow noreferrer">https://cp -algorithms.com / algebra / all-submasks.html и получить сложность O(3^n) (хорошая работа для n <= ~ 18). Начальный <code>F[0] = 0 и ответ F[2^n - 1].