Разделяй и властвуй, чтобы найти максимальную сумму подсписка списка - PullRequest
Новая
       13

Разделяй и властвуй, чтобы найти максимальную сумму подсписка списка

0 голосов
/ 03 сентября 2018

Учитывая список L, два элемента, которые находятся рядом в списке, нельзя одновременно выбрать в подсписке S, а список L не содержит повторяющихся значений. Я хочу разработать алгоритм с использованием подхода «разделяй и властвуй», который выводит подсписок S, максимизирующий сумму его элементов. Например, если L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13], то S = [1, 5, 7, 15, 13]. Следующие коды, которые я написал, не работают, и я думаю, что это не подход «разделяй и властвуй». 

def bestsublist(l):
    sublist = []
    n = len(l)
    totalsum = [None] * (n + 1)
    totalsum[n] = 0
    for i in range(n-1,-1,-1):
        totalsum[i] = max(l[i] + totalsum[min(i+2,n)],totalsum[min(i+1,n)])
        if l[i] + totalsum[min(i+2,n)] > totalsum[min(i+1,n)]:
            sublist.append(l[l[i] + totalsum[min(i+2,n)] - 1])
        else:
            sublist.append(l[totalsum[min(i+1,n)] - 1])

    return sublist

1 Ответ

0 голосов
/ 03 сентября 2018

Ваше решение почти правильное. Единственное, что не так с этим - это то, как вы строите подсписок решений.

Проблема в том, что вы добавляете его до того, как закончите обход всего списка, поэтому вы еще не знаете, собираетесь ли вы использовать элемент или нет.

Так что, чтобы исправить это, просто запустите список снова и создайте подсписок. Вот как это будет выглядеть: 

....
for i in range(n-1,-1,-1):
    totalsum[i] = max(l[i] + totalsum[min(i+2,n)],totalsum[min(i+1,n)])

i = 0
while i < n:
   if l[i] + totalsum[min(i+2,n)] > totalsum[min(i+1,n)]:
        sublist.append(l[i])
        i += 2
    else:
        i += 1
return sublist

P.s. Ваше решение - динамическое программирование, а не «разделяй и властвуй».

...