更多动态规划

Question

两周前，我发帖 question here about dynamic programming. User Andrea Corbellini 准确回答了我想要的问题，但我想更进一步解决这个问题。

这是我的功能

def Opt(n):
    if len(n) == 1:
        return 0
    else:
        return sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                            for i in range(1, len(n)))

假设你会打电话给

Opt( [ 1,2,3,4,5 ] )

上一题解决了计算最优值的问题。现在，我不想为上面的例子计算最佳值 33，而是想打印出我们获得最佳解决方案的方式（最佳解决方案的路径）。所以，我想打印列表得到 cut/divided 的索引，以列表的形式获得最佳解决方案。所以，上面例子的答案是：

[ 3,2,1,4 ]（在第三个 marker/index 处剪切 pole/list，然后在第二个索引之后，然后在第一个索引之后，最后在第四个索引处）。也就是说答案应该是列表的形式。列表的第一个元素将是列表的第一个 cut/division 应该出现在最佳路径中的索引。第二个元素将是列表的第二个 cut/division，依此类推。

也可以有不同的解决方案：

[ 3,4,2,1 ]

它们仍然会引导您获得正确的输出。所以，你打印哪一个并不重要。但是，我不知道如何跟踪和打印动态规划解决方案采用的最佳路径。顺便说一句，我想出了一个非递归的解决方案来解决我上一个问题中解决的那个问题。但是，我仍然无法弄清楚打印最佳解决方案的路径。这是上一题的非递归代码，可能对解决当前问题有帮助。

def Opt(numbers):
prefix = [0]
for i in range(1,len(numbers)+1):
    prefix.append(prefix[i-1]+numbers[i-1])
results = [[]]
for i in range(0,len(numbers)):
    results[0].append(0)
for i in range(1,len(numbers)):
    results.append([])
    for j in range(0,len(numbers)):
        results[i].append([])
for i in range(2,len(numbers)+1): # for all lenghts (of by 1)
    for j in range(0,len(numbers)-i+1): # for all beginning
        results[i-1][j] = results[0][j]+results[i-2][j+1]+prefix[j+i]-prefix[j]
        for k in range(1,i-1): # for all splits
            if results[k][j]+results[i-2-k][j+k+1]+prefix[j+i]-prefix[j] < results[i-1][j]:
                results[i-1][j] = results[k][j]+results[i-2-k][j+k+1]+prefix[j+i]-prefix[j]
return results[len(numbers)-1][0]

Answer 1

这是打印所选内容的一种方法：

我在你之前的问题中使用了@Andrea Corbellini 提供的使用记忆的递归解决方案。如下所示：

cache = {}

def Opt(n):
    # tuple objects are hashable and can be put in the cache.
    n = tuple(n)

    if n in cache:
        return cache[n]

    if len(n) == 1:
        result = 0
    else:
        result = sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                              for i in range(1, len(n)))

    cache[n] = result
    return result

现在，我们有了所有元组的缓存值，包括选定的元组。

使用它，我们可以打印选定的元组，如下所示：

selectedList = []
def printSelected (n, low):

    if len(n) == 1:
        # No need to print because it's 
        # already printed at previous recursion level.
        return

    minVal = math.Inf
    minTupleLeft = ()
    minTupleRight = ()
    splitI = 0

    for i in range(1, len(n)):
        tuple1ToI = tuple (n[:i])
        tupleiToN = tuple (n[i:])

        if (cache[tuple1ToI] + cache[tupleiToN]) < minVal:
            minVal = cache[tuple1ToI] + cache[tupleiToN]
            minTupleLeft = tuple1ToI
            minTupleRight = tupleiToN
            splitI = low + i


    print minTupleLeft, minTupleRight, minVal
    print splitI   # OP just wants the split index 'i'.
    selectedList.append(splitI) # or add to the list as requested by OP

    printSelected (list(minTupleLeft), low)
    printSelected (list(minTupleRight), splitI)

你调用上面的方法如下所示：

printSelected (n, 0)

更多动态规划

More on dynamic programming

python

dynamic-programming

memoization