0-1 Рюкзак с пенальти для случаев с недостаточным весом и избыточным весом

Question

Предположим, что классическая проблема с рюкзаком 0-1, но вам разрешено переполнять мешок с небольшим штрафом. Прибыль от X вычитается для каждого переполнения единицы (масса выше максимальной мощности), а прибыль Y вычитается для каждого нижестоящего устройства (масса ниже максимальной емкости).

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

Это решение не работает в некоторых случаях, например, когда есть 3 предмета с весом 30,20,10 и прибыль 30, 25, 20 соответственно. Максимальный допустимый вес - 39, штраф за нисходящий поток - 5, а штраф за переполнение - 10.

Мое решение состояло в том, чтобы разрешить его, как обычный рюкзак, затем с учетом штрафов, поэтому он дает решение выбирать предметы весом 20,10, добавьте элемент веса 30, поскольку его штраф больше, чем прибыль. Оптимальным решением должно быть выбор предметов весом 30 и 10. Единственное, о чем я могу думать сейчас, - это грубая сила, которой следует избегать, если это возможно. Если бы кто-нибудь мог подумать о каком-либо другом решении, это было бы здорово!

Answer 1

Вы можете разбить его на две подзадачи: одну с пониженным весом и одну с надбавкой в ​​избыточном весе. Более конкретно, вы можете решить эту проблему путем решения двух различных integer linear programming problems, и взяв лучшее из двух решений:

Скажите, что у вас есть n элементов весов w1,w2,...,wn и значение v1, v2, ..., vn. Скажем, что весовая грузоподъемность C, штраф за недостоверность A, а предел за превышение веса - B (за единицу).

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

Задача 1)

max v1*x1 + v2*x2 + ... + vn*xn - A*(C - w1*x1 - w2*x2 - ... - wn*xn) 

subject to 

w1*x1 + w2*x2 + ... + wn*xn <= C 

Обратите внимание, что с помощью алгебры целевой функции такой же, как аффинного выражение

(v1 + A*w1)*x1 + ... + (vn + A*wn)*xn - A*C 

и достигает максимум при тех же значений x1, ..., xn, которые обеспечивают максимальных чисто линейную функцию

(v1 + A*w1)*x1 + ... + (vn + A*wn)*xn 

Эта подзадача может быть решена с использованием y ILP, или как обычная проблема с рюкзаком.

Задача 2)

max v1*x1 + v2*x2 + ... + vn*xn - B*(w1*x1 + w2*x2 + ... + wn*xn - C) 

subject to 

w1*x1 + w2*x2 + ... + wn*xn >= C 

, которая может быть решена путем максимизации линейной целевой функции

(v1 - B*w1)*x1 + ... + (vn - B*wn)*xn 

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

On Edit. Вторая проблема также может быть решена как проблема с рюкзаком - одна, в которой вы решаете, какие элементы не включать. Начните с решения, в которое вы включаете все. Если это невозможно (если сумма всех весов не превышает емкость), тогда вы закончите. Решение задачи 1 является глобальным решением. В противном случае. Определить избыток, S, чтобы быть

S = w1 + w2 + ... + wn - C 

Теперь решить следующую задачу о рюкзаке:

weights: w1, w2, ..., wn //same as before 
values: Bw1 - v1, Bw2 - v2, ..., BWn - vn 
capacity: S 

Слово о значениях: Bwi - vi является мерой того, насколько удаление го объект помогает (в предположении, что удаление его держит вас выше первоначальной емкости, так что вам не нужно учитывать штрафы с недостаточным весом). С одной стороны, он снимает часть штрафа, Bwi, но с другой стороны это берет некоторое значение, vi.

После того как вы решите проблему с рюкзаком - удалите эти предметы. Остальные элементы являются решением для задачи 2.

Давайте посмотрим, как это играет для вашей проблемы игрушек:

weights: 30, 20, 10 
values: 20, 25, 20 
C: 39 
A: 5 //per-unit underflow penalty 
B: 10 //per-unit overflow penalty 

Для задачи 1, решить следующую задачу о рюкзаке:

weights: 30, 20, 10 
values: 170, 125, 70 // = 20 + 5*30, 25 + 5*20, 20 + 5*10 
C: 39 

Этот имеет решение: включает 20, 10 со значением 195. В терминах исходной задачи это имеет значение 195 - 5 * 39 = 0. Это кажется немного странным, но с точки зрения исходной проблемы значение использования двух последних элементов составляет 25 + 20 = 45, но он оставляет вас 9 единиц с штрафом 5 * 9 = 45 и 45 - 45 = 0

Вторая проблема:

weights: 30, 20, 10 
values: 280, 175, 80 // = 10*30 - 20, 10*20 - 25, 10*10 - 20 
S: 26 // = 30 + 20 + 10 - 39 

Решение этой проблемы, очевидно, чтобы выбрать 20. Это означает, что 20 выбрано для невключения. Это означает, что для второй задачи я хочу включить объекты весов 30 и 10.

Значение этого является (в терминах исходной задачи)

20 + 20 - 10*1 = 30 

Так как 30> 0 (значение решения 1), это общее оптимальное решение.

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

Answer 2

Вы все еще можете использовать стандартное динамическое программирование.

1. Давайте вычислим ли сумма s достижим для всех s от 0 к сумме всех элементов массива. Это то, что делает стандартное решение динамического программирования. Здесь нас не волнует наказание.

2. Давайте перебираем все доступные суммы и выбираем лучший, учитывая штраф за превышение (или под) потока.