Как сложить все значения массивов с другими значениями массивов в двухмерном массиве?

Question

[Idwln]

Задача:

Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 23.

3
7 4
2 4 6
8 5 9 3

То есть, 3 + 7 + 4 + 9 = 23.

Найдите максимальную сумму пути от вершины до основания следующего треугольника:
(Треугольник будет в решении)

Мой код:

line = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
data = line.split('\n')
arr = []
for line in data[::-1]:
    arr.append(line.split(' '))
arr_for_summary = []
ind = 0
arr2 = []
arr3 = []
for a in arr:
    for b in a:
        if len(a) > 1:
            c = arr[arr.index(a)+1]
        else:
            break
        if ind < len(c):
            res = int(b) + int(c[ind])
            if b not in arr2:
                res2 = int(a[a.index(b) + 1]) + int(c[ind])
            else:
                res2 = int(a[a.index(b,arr2.index(b)) + 1]) + int(c[ind])
            arr_for_summary.append(res)
            arr_for_summary.append(res2)
            arr2.append(b)
            ind+=1
        else:
            break
    if arr_for_summary:
        arr3.append(arr_for_summary)
    arr_for_summary = []
    arr2 = []
    ind = 0
    arr.pop(0)
arr3.append([75])

for row in arr3:
    print(row)

Мой алгоритм основывавается на том, чтобы найти сумму всех чисел в каждых 2-ух рядах, и получить двухмерный массив, в котором суммы 1-го и 2-го ряда, 3-го и 4-го ряда и т.д

Вот что получается при выводе:

[67, 125, 128, 164, 102, 31, 95, 91, 112, 98, 62, 123, 137, 165, 128, 57, 146, 166, 109, 54, 107, 122, 140, 147, 100, 44, 35, 93]
[161, 141, 82, 63, 85, 71, 66, 45, 94, 91, 87, 164, 108, 88, 121, 136, 97, 89, 118, 95, 44, 46, 86, 105]
[94, 112, 119, 92, 116, 137, 98, 58, 72, 90, 75, 123, 128, 89, 68, 113, 191, 145, 80, 43]
[140, 140, 106, 106, 30, 60, 84, 111, 89, 46, 56, 96, 150, 140, 162, 125]
[107, 21, 3, 78, 100, 96, 148, 82, 10, 66, 97, 101]
[38, 22, 39, 117, 169, 134, 57, 75]
[112, 142, 111, 146]
[75]

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

result = 0
iterator = 0
for row in arr3:
    row2 = row[:]
    while len(row) > 1:
        max_number = max(row)
        index = row2.index(max_number)
        if iterator == 0 or index - previous_index == 0 or abs(index - previous_index) == 1:
            result += max_number
            previous_index = row.index(max_number) - 1
            iterator += 1
            row.remove(max_number)
            break
        row.remove(max_number)

print(result + 75)

Может найти лишь максимальную сумму при первом максимальном значении. Но вот как поменять первое максимальное значение несколько раз в ходе выполнения программы я не понимаю, т.к для проверки могу ли я сложить суммы рядов мне нужна переменная previous_index, а она получается только после 1-ой отработки программы. Вообщем я зашёл в тупик. Как это реализовать?

Мой ответ 1064, правильный 1074

Comments

[Алан Гибизов]

Во-первых, никогда не используйте однобуквенные имена переменных. Ничего же не понятно, каша буковок. Если строка - пишите row, колонка - column и т.п., а не a, b, c…
Во-вторых, хорошо бы разбить код на функции, и каждую отладить.
В-третьих, как соотносятся первый и второй коды, неясно.
И рекомендую код оборачивать при помощи кнопки </> с указанием ЯП. Тогда подсветка синтаксиса работает.

[fenrir]

Мой алгоритм основывавается на том, чтобы найти сумму всех чисел в каждых 2-ух рядах, и получить двухмерный массив, в котором суммы 1-го и 2-го ряда, 3-го и 4-го ряда и т.д

А куда вы дели сумму 2 и 3, 4 и 5 и т д?

Мой ответ 1064, правильный 1074

Как вы получили ответ, если ваша программа не отрабатывает?

Бонусом не понятно откуда вы взяли, что вы можете перескакивать просто по максимальным суммам, вы можете переходить только в соседние числа.
Сама форма треугольника в задаче предлагает использовать какой-нибудь из алгоритмов обхода графов, например алгорим Дейкстры, а не странное шаманство

Answer 1

[Gnifajio None]

Чтобы сложить все значения массива с другими значениями массива в двухмерном массиве, можно использовать цикл for для перебора элементов массива и суммировать их с помощью оператора +=.

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

total = 0
for row in array:
    for element in row:
        total += element

В данном случае, total будет содержать сумму всех элементов массива.

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

Для решения задачи можно использовать следующий код:

triangle = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20, 4, 82, 47, 65],
    [19, 1, 23, 75, 3, 34]
]

# создаем новый массив, который будет содержать максимальную сумму пути до каждой вершины
max_sums = triangle[-1]

# начинаем обработку с нижнего ряда треугольника
for i in range(len(triangle) - 2, -1, -1):
    # для каждой вершины в ряду выбираем максимальную сумму из соседних вершин в предыдущем ряду
    for j in range(len(triangle[i])):
        max_sums[j] = max(max_sums[j], max_sums[j + 1]) + triangle[i][j]

# максимальная сумма пути будет содержаться в первой вершине массива max_sums
print(max_sums[0])