алгоритм Рюкзак с 2 ограничениями

Question

Iv'e работал над проектом, и я столкнулся со следующим сценарием: Нужно выбрать N = 2 ящика из набора M, в то время как M> N с лучшей суммой весов, но с 2 ограничениями :

• Мы не можем выбрать один и тот же цвет коробки
• Мы не можем выбрать один и тот же идентификатор окна

Коробки приходит сортируется с наибольшим весом на вершине

Я выбираю (Red1, Blue2) с алгоритмом Naive, начиная с самого высокого веса Red1, мы не могли добавить Blue1, потому что у нас был тот же ID 1, и мы не могли добавить Red2, потому что у нас была Red box с весом 10, мы закончили с общим весом 11, но мы могли бы в конечном итоге с 18,9, если мы выбираем Blue1 & Red2 N может быть больше, чем 2.

Является ли это NP-трудной задачей? Любые лучшие решения с хорошей эффективностью во время работы?

Answer 1

Мы можем использовать DP решение со сложностью O(2^color * 2^id * M * N) или по отслеживанию + Обрезка со сложностью O(M choose N)

Так это зависит от того, насколько велика ограничение для M, N, цвет и ид.