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

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

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

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

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

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

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

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

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

Шарики:

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

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

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

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

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

Коробки:

1 красный (вмещает 1 шар)

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

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

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

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

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

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

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

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

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

Редактировать:

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

Редактировать 2:

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