项目Euler项目67 - Python

Question

注:我的英语很差，请不要对我评头论足:)

问题：

/问题=18

/问题=67

我正在用Python做Euler #67项目。我的计划，为项目18工作，不适用于项目67。代码(不包括打开文件和处理信息)：

for i in range(len(temp)):
    list1 = temp[i]
    try:
        list2 = temp[i+1]
        trynum1 = list1[lastinput] + max(list2[lastinput],list2[lastinput+1])
        try:
            trynum2 = list1[lastinput+1] + max(list2[lastinput+1],list2[lastinput+2])
            if trynum1 > trynum2:
                outputlist.append(list1[lastinput])
            else:
                outputlist.append(list1[lastinput+1])
                lastinput += 1
        except IndexError:
            outputlist.append(list1[0])
    except IndexError:
        if list1[lastinput] > list1[lastinput+1]:
            outputlist.append(list1[lastinput])
        else:
            outputlist.append(list1[lastinput+1])

变量：

temp是整数的三角形

outputlist是存储程序选择的数字的列表。

我知道答案是7273，但我的程序发现6542。我找不到造成这种情况的错误。请你帮我一把，因为我已经在这个项目上抓头发了，几乎所有的头发都从我头上掉下来了。

逻辑

我对这个程序的方法是找到一个数字(list1lastinput)，并将其与它下面两个数字中较大的一个(trynum1)相加，与第一个数字(list1lastinput+1)右边的数字进行比较，在它下面(trynum2)添加更大的两个数字。我将较大的一个附加到输出列表中。

Answer 1

这种方法在逻辑上是有缺陷的。当您在第1行时，您没有足够的信息来知道向右或向左移动是否会导致最大和，而不是仅用2行向前看。你需要一直往下看，以确保得到最好的路径。

正如其他人所建议的那样，从底部开始，向上努力。记住，你不需要整条路，只需要和。在每个节点上，添加两个可用路径中较好路径的数量(这是将该节点带到底部所获得的分数)。当你回到顶端的时候，临时工，这个数字应该是你的最终答案。

Answer 2

我日日夜夜地思考着问题18，我解决了它，就像我解决这个问题一样。P.S. 100_triangle.txt没有第一个字符串'59‘。

# Maximum path sum II
import time
def e67():
    start = time.time()
    f=open("100_triangle.txt")
    summ=[59]
    for s in f:
        slst=s.split()
        lst=[int(item) for item in slst]
        for i in range(len(lst)):
            if i==0:
                lst[i]+=summ[i]
            elif i==len(lst)-1:
                lst[i]+=summ[i-1]
            elif (lst[i]+summ[i-1])>(lst[i]+summ[i]):
                lst[i]+=summ[i-1]
            else:
                lst[i]+=summ[i]
        summ=lst
    end = time.time() - start
    print("Runtime =", end)
    f.close()
    return max(summ)
print(e67()) #7273

Answer 3

虽然从底部开始更有效率，但我想看看是否可以在这个问题上实现Dijkstra的算法；它工作得很好，只需几秒钟(没有精确地计时)：

from math import inf

f = open("p067_triangle.txt", "r")
tpyramid = f.read().splitlines()
f.close()

n = len(tpyramid)

pyramid = [[100 - int(tpyramid[i].split()[j]) for j in range(i+1)] for i in range(n)]

paths = [[inf for j in range(i+1)] for i in range(n)]
paths[0][0] = pyramid[0][0]

def mini_index(pyr):
    m = inf
    for i in range(n):
        mr = min([i for i in pyr[i] if i >= 0]+[inf])
        if mr < m:
            m, a, b = mr, i, pyr[i].index(mr)
    return m, a, b

counter = 0

omega = inf

while counter < n*(n+1)/2:
    min_weight, i, j = mini_index(paths)
    if i != n-1:
        paths[i+1][j] = min( paths[i+1][j], min_weight + pyramid[i+1][j])
        paths[i+1][j+1] = min( paths[i+1][j+1], min_weight + pyramid[i+1][j+1])
    else:
        omega = min(omega, min_weight)
    paths[i][j] = -1
    counter += 1
    
print(100*n - omega)