题目67：使用高效算法找到三角形中的最大和。
本帖最后由 欧拉计划 于 2015-10-14 15:45 编辑Maximum path sum II
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there arealtogether! If you could check one trillionroutes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
题目：
从以下三角形的顶端开始，向下一行的相邻数字移动，从顶端到底端的最大总和是 23 。
也就是 3 + 7 + 4 + 9 = 23。
(右键另存为)是一个文本文件，包含了一个一百行的三角形，找出这个三角形中从顶到底的最大和。
注意：这是题目 18 的更难的一个版本。穷举每一种可能的路径是不可行的，因为一共有条可能的路径。就算每秒钟能处理条路径，也需要 200 亿年来处理完所有的路径。存在一个高效的方法来处理这道题。
本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:48 编辑
7273
lst =[
['59'],
...,
['23','33','44','81','80','92','93','75','94','88','23','61','39','76','22','03','28','94','32','06','49','65','41','34','18','23','08','47','62','60','03','63','33','13','80','52','31','54','73','43','70','26','16','69','57','87','83','31','03','93','70','81','47','95','77','44','29','68','39','51','56','59','63','07','25','70','07','77','43','53','64','03','94','42','95','39','18','01','66','21','16','97','20','50','90','16','70','10','95','69','29','06','25','61','41','26','15','59','63','35']]
dic = {'00':0,'01':1,'02':2,'03':3,'04':4,'05':5,'06':6,'07':7,'08':8,'09':9}
lstnew = lst[:]
for x in range(100):
for j in range(x+1):
if lst == '00' or lst == '01' or lst == '02' or lst == '03' or lst == '04' or lst == '05' or lst == '06' or lst == '07' or lst == '08' or lst == '09':
lstnew = dic]
else:
lstnew = int(lst)
for y in range(1,100):
for z in range(y+1):
if z == 0:
lstnew += lstnew
elif z == y:
lstnew += lstnew
elif lstnew < lstnew:
lstnew += lstnew
else:
lstnew += lstnew
print (max(lstnew))
另外一种，最优化求解的方法（可以适用多路径最优求解）：
#coding:utf-8
#initiate:
file=open('triangle.txt')
f=file.read()
file.close()
s=f.split('\n')
triangle = [[]*(i+1) for i in range(100)]
for i in range(100):
triangle=s.split()
for i in range(100):
for j in range(i+1):
triangle=int(triangle)
#print (triangle)
visited = [*(i+1) for i in range(100)]
dp = [*(i+1) for i in range(100)]
move = [(1,0),(1,1)]
checklist = [(0,0)]
dp = 59
#define method to search the best way:
def findway(x,y):
if not visited:
visited = True
for m in move:
nx,ny = x+m,y+m
if 0<=nx<100 and 0<=ny<=nx:
dp = max(dp+triangle,dp)
checklist.append((nx,ny))
#max9999 is the max price to go:
max9999 = 0
#repeat again and again until the max is stable, that's the answer.
while True:
for i in range(len(checklist)):
findway(checklist,checklist)
if len([(j,k) for j in range(100) for k in range(j) if not visited]) == 0:
visited = [*(i+1) for i in range(100)]
checklist = [(0,0)]
if max9999 < max(dp):
max9999 = max(dp)
else:
print (max9999)
break # encoding:utf-8
# 计算三角形最长路径
from time import time
def readFile():
data = []
with open('p067_triangle.txt') as f:
for line in f:
tmp =
data.append(tmp)
return data
def euler067():
data = readFile()
for i in range(len(data) - 2, -1, -1):
for j in range(0, len(data)):
if data + data > data + data:
data = data + data
else:
data = data + data
print(data)
if __name__ == '__main__':
start = time()
euler067()
print('cost %.6f sec' % (time() - start))
7273
cost 0.017002 sec
data67.csv中数据的格式：
59
73,41
52,40,09
26,53,06,34
10,51,87,86,81
61,95,66,57,25,68
90,81,80,38,92,67,73
30,28,51,76,81,18,75,44
……
import csv
nums = []
with open('data67.csv') as f:
reader = csv.reader(f)
for row in reader:
nums.append(row)
list1 = []
i = len(nums)-1
# 先处理最后一行，选择相邻两个数中大的那个，将其位置、数值放入list1列表中
for j in range(i):
a = nums
b = nums
if a > b and not in list1:
list1.append()
elif b > a and not in list1:
list1.append()
# 从倒数第二行开始，依次向上处理
while i > 0:
dict1 = {}
i = i-1
# 将list1中每个数字的上一行的相邻两个（或一个）数字加到字典dict1中
for each in list1:
j = each
if j == 0: # 处理每行处于第一列的数字
dict1.setdefault((i,j),[]).append(int(nums)+int(each))
elif j == i+1: # 处理每行处于最后一列的数字
dict1.setdefault((i,j-1), []).append(int(nums)+int(each))
else: # 处理中间的数字，由于中间的数字在上一行都会对应两个相邻数字，所以要增加一种情况
dict1.setdefault((i, j), []).append(int(nums)+int(each))
dict1.setdefault((i, j - 1), []).append(int(nums)+int(each))
# 将字典转换为列表，并选择较大的那个数值
list1 = []
for each in dict1:
list1.append(, each, max(dict1)])
print(list1)
7273
0:00:00.015637
本帖最后由 fc1735 于 2020-2-21 17:01 编辑
from functools import reduce
f = open('67.txt')
t = f.read()
t = list(map(lambda x: list(map(lambda y: int(y), x.split())),
filter(lambda x: len(x) != 0, t.split('\n'))))
print(max(reduce(lambda x, y: list(map(lambda a, b: a + b, map(max, + x, x + ), y)), t)))
https://github.com/devinizz/project_euler/blob/master/page02/67.py 7273
Process returned 0 (0x0) execution time : 0.049 s
Press any key to continue.
动态规划（dp）经典题，状态转移方程为
https://wx3.sinaimg.cn/mw690/0081qlg6ly1ghfpxooggmj30nm01gq2w.jpg
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int M = 100 + 5;
int a;
int opt;
int dp(int i,int j){
if (opt >= 0) return opt;
if (i == 100-1) return opt = a;
return opt = a + max(dp(i+1,j),dp(i+1,j+1));
}
int main(){
freopen("i.in","r",stdin);
memset(opt,-1,sizeof(opt));
for (int i = 0;i < 100;i++){
for (int j = 0;j <= i;j++){
cin >> a;
}
}
cout << dp(0,0) << endl;
return 0;
}
C++#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
using vecus = vector<unsigned short>;
unsigned int max(const vecus& v) {
unsigned int result = 0;
for (auto i : v) {
if (i > result) {
result = i;
}
}
return result;
}
void scan(ifstream& file, vecus& v, size_t count) {
unsigned short t;
for (size_t i = 0; i < count; i++) {
file >> t;
v = t;
}
}
void add(const vecus& a, vecus& b) {
size_t i;
b += a;
for (i = 1; i < a.size(); i++) {
b += max(a, a);
}
b += a;
}
int main() {
ios::sync_with_stdio(false);
ifstream file("C:\\Users\\WWW\\Desktop\\0\\p067_triangle.txt");
constexpr static size_t N = 100;
vecus a(N), b(N);
scan(file, b, 1);
for (size_t line = 2; line <= N; line++) {
swap(a, b);
scan(file, b, line);
add(a, b);
}
cout << max(b) << endl;
return 0;
} #include <iostream>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
int Array[]={
#include "p067_triangle.txt"
};
#define width 100
void setmax(int i,int j)
{
if(j == 0)
Array += Array;
else if(j == i)
Array += Array;
else
Array += max(Array,Array);
}
int main()
{
for(int i=1;i<width;i++)
for(int j=0;j<=i;j++)
setmax(i,j);
int maxum = 0;
for(int i=width*(width-1)/2+0;i<width*(width-1)/2+width;i++)
if(maxum<Array)
maxum = Array;
cout << maxum;
} import time as t
start = t.perf_counter()
with open('C:/Users/50598/Desktop/p067_triangle.txt', 'r') as f:
file = f.read().splitlines()
nums = []
for each_row in file:
nums.append()
for i in range(len(nums) - 2, -1, -1):
for j in range(i + 1):
if nums > nums:
nums += nums
else:
nums += nums
print(nums)
print("It costs %f s" % (t.perf_counter() - start))
7273
It costs 0.002033 s
页:
[1]