алгоритм: выберите число из каждого списка, найдите самую большую сумму

, если у нас есть n списков, нам нужно выбрать число из каждого списка, выбранный номер не может быть выбран снова, как сделать выбор, чтобы получить самую большую сумму n выбранных номеров? , например.алгоритм: выберите число из каждого списка, найдите самую большую сумму

list1: 4 5 7. 
list2: 3 5 7. 
list3: 1 5

если выбрать 7 из list1, наибольшее количество можно выбрать в списке 2 является 5 (потому что тот же номер не может быть выбран в два раза), если выбрать 5 из list2, можно выбрать только 1 из List3, поэтому сумма равна 7+5+1=13

это НЕ лучший выбор. однако, если мы выберем 4 из списка1, 7 из списка2, 5 из списка3, сумма равна 4+7+5=16

Есть ли алгоритм, чтобы найти лучший способ сделать выбор, чтобы получить самую большую сумму? Решение должно быть идеальным.

источник

2013-03-22 Yijie Li

Возможно, алгоритм Knuth's «Dancing Links»? – comocomocomocomo

Это может быть NP-трудная проблема, которая всегда будет оптимально решаться. ваше решение должно быть совершенным или просто нужно быть хорошим? – Wug

Можно ли считать, что каждая строка уже отсортирована? – jamylak

Для этого нет прямого алгоритма, однако проблема может быть решена за полиномиальное время путем изменения венгерского алгоритма. WIKI

Нам дано неотрицательное N × N матрице, где элемент в г-й строке и j-й столбец представляет стоимость присвоения J-го задания, чтобы I-го рабочего. Мы должны найти задание рабочих мест для работников с минимальными затратами. Если цель состоит в том, чтобы найти назначение , что дает максимальную стоимость, проблема может быть изменена, чтобы соответствовать настройке , заменив каждую стоимость максимальной стоимостью, вычитаемой стоимостью .

Построить матрицу размерности (K * K), где K = max (n, максимальное количество элементов в списке).

Например:

List 1=1 2 3 4 
List 2=5 
List 3=9 10 

The K*K matrix is: 
1 2 3 4 
5 0 0 0 
9 10 0 0 
0 0 0 0

Примените следующий алгоритм http://en.wikipedia.org/wiki/Hungarian_algorithm#Setting приведенной выше матрицы.

источник

2013-03-22 06:19:56

Есть ли лучшее решение, чем полиномиальное время? –

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

Это не похоже на ту же проблему.Это имеет ограничение, что один и тот же * столбец * не может использоваться дважды, тогда как OP ограничивает использование одного и того же * значения * дважды. – RBarryYoung

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

List1 : 2 2 2 
List2 : 2 2

Нам не нужно перебирать все числа в списке. В худшем случае мы столкнулись с числами n-1, которые мы видели раньше. Нравится:

list1: 5 6 7 
list2: 5 6 7 
list3: 5 6 7

Итак, я бы сделал это;

for list in lists: 
    max = list[len(list)] 
    possible_result.append(max) 
    for j = len(list) to j = len(list)-n in other lists: 
     max = list[j] 
     if not max exist in possible_result: 
      append to possible_result 
Find largest possible_result

Первая итерация будет выполняться n раз второй, в худшем случае, n-1 раз.

источник

2013-09-22 16:27:08 NiceCoder

алгоритм: выберите число из каждого списка, найдите самую большую сумму

ответ

Смежные вопросы