Эта проблема NP-сложная?

Question

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

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

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

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

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

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

---

Изменить - вот простой пример:

Шарики:

• 1 красный шар - 5 баллов
• 1 синий шар- 3 балла
• 1 зеленый / красный шар - 2 балла
• 1 зеленый / синий шар - 4 балла
• 1 красный / синий шар - 1 балл

Коробки:

• 1 красный
• 1 синий
• 1 зеленый

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

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

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

  Общая стоимость: 12 баллов(5 + 3 + 4)

Answer 1

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

Алгоритм назначения может быть решен за O (n ^ 3) временигде n здесь - максимальное количество шаров или ящиков, используя венгерский алгоритм .(Кстати, я должен сделать заявление об отказе от ответственности, в котором я упоминаю только венгерский алгоритм, потому что это теоретический результат, с которым мне довелось быть знакомым, и он, вероятно, отвечает на вопрос в заголовке о том, является ли исходная проблема NP-трудной.лучший ли это алгоритм для использования на практике.)

Answer 2

Вы пробовали жадный алг?Сортируйте по пунктам / значению и поместите в поле, если это возможно.Если есть какие-то исключения, я пропускаю id, чтобы увидеть их.