Представьте, что есть n заданных наборов, каждый из которых содержит m элементов. Каждый вес комбинации двух элементов из разных наборов задан (это означает, что у нас есть m ^ n два на два веса комбинации). Задача состоит в том, чтобы выбрать n элементов из n различных наборов (по одному элементу из каждого набора), который имеет максимальную сумму их двух по двум комбинационным весам. Аппроксимация в порядке.
, например, приведены наборы A, B и C, а также их удвоенная комбинация весов их элементов. Найдите 3 элемента (один из A, один из B и один из C), который имеет максимальную сумму их двух на два комбинированных веса с хорошим приближением (85-95%).
У меня есть думал о возможном ответе, но я не знаю, насколько это точно. Я говорю, что мы можем начать с максимума двух до двух комбинационных весов (и ясно, что мы знаем, для каких двух элементов, например, они названы a1 из набора A и b1 из набора B), а затем найти максимум суммы два на два комбинированных веса (a1 и элементы других наборов (кроме B) + b1 и элементы других наборов (кроме A). мы продолжаем делать это для всех оставшихся наборов.
Пожалуйста, скажите мне если вы знаете ответ на основную проблему или знаете, насколько точен мой ответ.
Кроме того, если бы вы могли сказать мне, как я могу кодировать ответ с помощью Python или JavaScript, я буду очень рад .
Спасибо