java - 用动态规划解决桥梁和 torch 难题

Question

我正在尝试使用动态编程解决类似桥梁和 torch 的问题。有关此问题的更多信息，请参见维基百科 (http://en.wikipedia.org/wiki/Bridge_and_torch_problem)。故事是这样的:

Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. They have one torch and, because it's night, the torch has to be used when crossing the bridge. Person A can cross the bridge in one minute, B in two minutes, C in five minutes, and D in eight minutes. When two people cross the bridge together, they must move at the slower person's pace. The question is, can they all get across the bridge in 15 minutes or less?

现在我已经设法使用图来解决问题，但我不知道如何使用动态规划来解决此类问题。您如何将问题分解为子问题？以及子问题的解如何导致整个问题的最优解？有哪些阶段和状态？

有人知道如何使用 DP 解决这个问题吗？也许告诉我如何用 Java 解决这个难题？

Answer 1

我已经用 python 为 torch 和桥梁拼图编写了代码，您可以在其他语言中使用相同的逻辑。

src=[1,2,5,8]

src=sorted(src)


def minimum_time(src):
    
    count=0
    if len(src)==3:
        count=sum(src)
    else:
        count=src[1]*(len(src)-2)+src[0]*(len(src)//3)
        for i in range(len(src)-1,-1,-2):
            #print(src[i])
            count+=src[i]
    return(count)

print(minimum_time(src))