Взять уникальные карточки из каждой колоды с максимальной суммой на выходе

[kangreon]

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

И нарисовал небольшую иллюстрацию задачи:

[Аватар]

Задача не понятна. Какая информация есть о содержимом колод?

[rrrFer]

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

Ну а дальше... можно попробовать даже полный перебор (если цветов и колод не десятки).
Если не пройдет - улучши перебор при помощи жадного алгоритма.

Задача стопудово сводится к поиску остовного дерева, но как эффективно его сюда вкрутить чтобы оценка была O (E*log V), не скажу. т.к. уже опаздываю ).

Если нужно E log V - то задача не очень тривиальная, готовый код просто так врядли кто-то выложит ))

[rrrFer]

Ошибся я вроде бы. Остовное дерево к задаче отношения не имеет. Ничего лучше алгоритма ветвей и границ я по задаче не придумал. Оно точно есть?
Т.е. находишь первый вариант решения задачи, затем ищешь вариант, который улучшит текущий. Если на каком то шаге стало понятно, что улучшить не получится - дальше не перебираешь (поднимаешься по дереву решений вверх и пробуешь другую ветвь)

[Аватар]

Тоже кроме задачи коммивояжера примерно по такому графу в голову ни чего не приходит

[rrrFer]

Это не комивояжер (поэтому и не подойдут остовные деревья). Пусть может содержать только по одной точке разных цветов. При переходе часть дуг как бэ удаляется, но при этом изначально дуг зверски много - порядка V^{V-1}.

[Utkin]

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

[Sibedir]

kangreon, поясни на примере
Вот есть
Карточки.jpg
Каков будет верный ответ?
1. Не получается, так как в "максимальном" наборе есть одинаковые цвета
Не получается.jpg
Или
2. Вот такие наборы имеют максимальную сумму при разных по цвету карточках
Получается.jpg
или
И так тоже получается.jpg

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

[Utkin]

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

[Аватар]

Имеется в виду перебор всех возможных вариантов выбора. Вот без него как? Как выше предложено в каждой колоде оставить по одной карте каждого цвета с максимальным весом. Переходы начинать с колоды с минимальным количеством карт. Каждый переход часть оставшихся узлов и дуг отсекает. Почему нельзя назвать его вариантом задачи коммивояжера? Набор узлов и ветвей правда динамически меняется, но в сторону уменьшения, в процессе перебора