如何获取最大三角形路径和的轨迹？

此问题来自Euler project - 18。

我通过最大总和和获得总和的路径来解决这个问题。

在这种情况下

，答案是1+8+2+5=16和c(-1,1,-1)（↓是-1和↘为1）

我知道由其中获得最大总和的代码。

chart[2, 1:2] <- chart[2, 1:2] + chart[1, 1] 
for (i in 3:n) { 
    chart[i, 1] <- chart[i, 1] + chart[(i - 1), 1] 
    chart[i, i] <- chart[i, i] + chart[(i - 1), (i - 1)] 
    for (j in 2:(i - 1)) { 
     chart[i, j] <- chart[i, j] + max(chart[(i - 1), (j - 1):j])` 
     } 
    } 
} 
result <- max(chart[n, ])

Here此代码

的说明页面，但我不知道所获得的最大一笔the path的代码。

来源

2015-09-27 kmee

你应该自己解决项目欧拉问题。这就是它的重点。 – Heroka

OP的问题与确定路径有关，该路径不是欧拉18问题的一部分 - 该问题只是想知道_sum_，而不是路径，所以这是完全正确的问题。 – rbm

你总是可以回溯。例如：

n <- 4 
chart <- read.table("chart2.txt", sep = " ", fill = NA, col.names = 1:n) 
chart <- as.matrix(chart) 
original <- chart # keep the original pyramid 

chart[2, 1:2] <- chart[2, 1:2] + chart[1, 1] 
for (i in 3:n) { 
    chart[i, 1] <- chart[i, 1] + chart[(i - 1), 1] 
    chart[i, i] <- chart[i, i] + chart[(i - 1), (i - 1)] 
    for (j in 2:(i - 1)) { 
    chart[i, j] <- chart[i, j] + max(chart[(i - 1), (j - 1):j]) 
    } 
} 
result <- max(chart[n, ]) 
cat("The result is:", result, "\n") 

# 
# get the path 
# 
route <- rep(0,n) # route will have n elements 
route[n] = which(chart[n,]==max(chart[n,],na.rm=TRUE))[[1]] # index of last max (in last row) 
route[1] = 1 # top of the pyramid 
for (i in (n-1):2) # starting from bottom, going to top 
{ 
    left <- if (route[i+1] > 1) route[i+1] -1 else 1 # index of left element 
    right <- if (route[i+1] < i+1) route[i+1] else i # index of right element 
    route[i] = which(chart[i,]==max(chart[i,left], chart[i,right], na.rm=TRUE))[[1]] # choose the higher value 
} 
cat("Route: ", route) 
checksum<-0; 
for (i in 1:n) checksum<-checksum+original[i, route[i]] 
cat("Checksum:", checksum)

执行时，这将打印

Route: 1 1 2 2 
Checksum: 16

执行用于欧拉（即n<-15）中的数据给出了

> cat("Route: ", route) 
Route: 1 2 3 3 3 4 4 4 5 6 7 8 9 9 10 
> cat("Checksum:", checksum) 
Checksum: 1074

（当然route是的实际索引每行的元素，可以很容易地变成+1和-1表示法。）

来源

2015-09-27 12:14:56 rbm

如何获取最大三角形路径和的轨迹？

回答

相关问题