Почему мой код не находит путь с наибольшей суммой?

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

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

03 
04 05 
02 03 06

и так далее. Я скопировал дерево в текстовый файл «набор данных», так это выглядело так:

03 
04 05 
02 03 06

, а затем анализируется его в 2d массив, но мои два вложенных для петель находит правильный ответ в примере, но не Главная проблема. Ответ проверяется компьютером, поэтому я не знаю, каким он должен быть.

tree = [[]] 
highest = 0 
f = open("dataset","r") #contains the data from the problem 

for line in f: #parser 
    for i in range(0,len(line),3): 
     tree[-1].append(int(line[i:i+2])) 
    tree.append([]) 
tree.pop() 

for i in range(len(tree)): 
    highest += tree[i][0] 

total = highest 

for j in range(1,len(tree)): 
    for i in range(len(tree)-1,j-1,-1): 
     print(i,j) 
     total -= tree[i][j-1] 
     total += tree[i][j] 
     if(total>highest): 
     highest = total 

print(highest)

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

Цикл double for использует общее количество всех левых, а затем вычитает последний номер из этой строки и добавляет новый. Он анализирует дерево справа налево.

Я думал, что это может быть ошибка границ, но я не вижу ее нигде.

Любая идея, где я ошибаюсь?

источник

2014-01-11 JFA

Не могли бы вы предоставить входы, ожидаемые выходы и фактические выходы? – jonrsharpe

Я не знаю ожидаемого результата в наборе данных, который я использую, потому что проблема проверяется компьютером. Выход для входа I, который я обнаружил, будет 3 + 5 + 6 = 14. Программа получает 14 для этого набора данных. Тем не менее, он не получает правильного ответа для больших наборов данных. – JFA

Вы не используете 'treeparser' ... Также вы не ограничиваете себя допустимыми путями. Боюсь, что все решение просто неправильно. – Veedrac

Ваше индексирование отключено.

for i in range(0,len(line),3):

даст вам, по линии

2 3 6

индексы 0 и 3; не0, 2 и 4. Принимая указательный и ломтика подход к этому не очень эффективно использовать split:

"2 3 6\n".strip().split(" ") == ['2', '3', '6']

Обратите внимание, что это будет работать, даже если включить двухзначных чисел.

Вы можете преобразовать все элементы в списке с помощью map:

map(int, ['2', '3', '6']) == [2, 3, 6]

источник

2014-01-11 19:53:22 jonrsharpe

Ваша последняя строка не решает проблему, но остальная часть полностью действительна. – Veedrac

А, да; Спасибо. – jonrsharpe

Прошу прощения, я дал вам неправильный набор данных. Я изменю его. Все данные в наборе - 2 цифры. – JFA

На размаху это:

tree = [ 
     [0], 
    [0,0], 
    [0,1,0], 
    [0,0,1,0] 
]

Ваш алгоритм не удается. Это легко увидеть: к тому времени, когда он доберется до 3, 2, он забыл 1 на 2, 1.

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

Я тестировал код с этим:

tree_node_cost = [ 
    ... 
] 

cost_cache = tree_node_cost[0] 

for row_node_costs in tree_node_cost[1:]: 
    out_cache = [0] * (len(cost_cache) + 1) 

    for i, cache in enumerate(cost_cache): 
     out_cache[i] = max(out_cache[i], row_node_costs[i] + cache) 
     out_cache[i+1] = row_node_costs[i+1] + cache 

    cost_cache = out_cache 

max(cost_cache)

как мой «проверенного» код и случайно сгенерированных деревьев, чтобы увидеть, что отличается, так что вы.

источник

2014-01-11 21:02:19 Veedrac

Почему мой код не находит путь с наибольшей суммой?

ответ

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