Разве это разрешимо в полиномиальном (или псевдополиномиальном) времени?

Я пытаюсь найти разумный алгоритм для этой проблемы:

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

Чтобы поместить мяч в коробку, он должен по крайней мере иметь цвет коробки на нем

(Например, вы можете поместить синий и зеленый шар в синюю коробку или зеленую коробку, но не в красную рамку.)

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

Мне просто любопытно, есть ли какой-то алгоритм динамического программирования для этого типа проблемы, чтобы сделать его разрешимым в полиномиальное время, или если это просто проблема коммивояжера в маскировке. Помогло бы мне, если бы я знал, что есть не более X цветов? Любая помощь приветствуется. Я мог бы также формализовать проблему немного с именами переменных, если это поможет. Спасибо!

Вот простой пример:

Максимальный вес: 5

Шарики:

1 красный шар - (value = 5, вес = 1)

1 синий шар - (value = 3, вес = 1)

1 зеленый/красный/синий шар - (value = 2, вес = 4)

1 зеленый/синий шар - (value = 4, вес = 1)

1 красный/синий шар - (value = 1, вес = 1)

Коробки:

1 красный (имеет 1 мяч)

1 синий (имеет 2 шара)

1 зеленый (имеет 1 шар)

Оптимальное решение:

красный шар в красном поле

синий шар и красный/синий шар в синем поле

зеленый/синий шар в зеленой коробке

Общее значение: 13 (5 + 3 + 1 + 4)

Общий вес: 4 (1 + 1 + 1 + 1)

Примечание: несмотря на то, что зеленый/красный/синий шар был более ценным, чем красный/синий шар, этот вес поставил бы нас над пределом.

Edit:

Один поясняющий момент: шары с одинаковой цветовой комбинацией не обязательно будут иметь одинаковые веса и значения. Например, у вас может быть красный шар со значением 3 и весом 1 и еще один красный шар со значением 2 и весом 5.

Изменить 2:

Мы можем принимать целочисленные веса и значения, если это помогает нам разработать алгоритм динамического программирования.

Ответ 1

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

В случае, когда шары с одинаковой комбинацией цветов должны иметь одинаковые веса и значения, рассмотрим случай, когда у вас есть красный/синий, красный/зеленый и т.д. шары и только один красный ящик.

Ответ 2

Если нет ограничений на количество ящиков, то эта проблема сильно NP-жесткая путем сокращения от 3-partition (настроено n/3 коробки и сделать все вещи радужными со значением = вес).

Если количество ячеек является постоянным, тогда существует алгоритм псевдополиномиального времени с помощью динамического программирования, где каждое состояние DP состоит из того, насколько заполнен каждый ящик.

Ответ 3

Сокращение от рюкзака выглядит следующим образом. Учитывая ваш экземпляр knapsack, вы создаете экземпляр проблемы с шарами и корзинами: для каждого элемента экземпляра ранца вы имеете шар с тем же весом и значением, что и элемент. Затем у вас есть коробка, представляющая рюкзак. Шары и коробка все голубые. Емкость коробки - это предел, заданный в задаче о рюкзаке. Учитывая решение вашей проблемы, у нас есть набор шаров в ящике, общий вес которого не превышает предела рюкзака, и общее значение которого максимизируется.

Ответ 4

Эта проблема NP-полная, потому что она включает проблему ранца.

То есть, это не просто похоже на проблему с рюкзаком: если есть одна чаша, все шары имеют этот цвет чаши, а максимальное количество шаров в чаше - общее количество шаров, тогда проблема в точности проблема с рюкзаком.

Если бы алгоритм мог решить эту проблему в полиномиальное время, он мог бы решить любую задачу ранца в полиномиальное время. Но, поскольку проблема с рюкзаком NP-полная, эта проблема тоже.

Ответ 5

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