动态编程无法给出正确答案 [英] Dynamic programming doesn't give correct answer

问题描述

我最近发现了一种称为动态编程的技术，但偶然发现了一个我无法解决的问题。开始时会为您提供一个参数列表，您需要做一些总结，就好像您要削减它一样。如果列表仅包含一个元素，则不对其进行汇总。如果还有更多，您可以对元素求和并以各种可能的方式进行削减。因此，如果list具有n个元素，则只有n-1种方法可以将其剪切。图片将说明：

I recently found out about the technique called dynamic programming and I stumbled upon a problem which I can't figure out. You are given a list of arguments in the beginning and you need to do sums on as if you were cutting it. If the list has only one element, you don't sum it. If it has more, you sum the elements and cut it in every possible way. So if list has n elements, there are just n-1 ways to cut it. The picture will explain:

我首先想总结一下所有可求和部分，我希望结果为20（11 + 9）（甚至认为正确答案是9），但我认为这将是一个不错的开始。但是我的代码返回数字37，我也不知道为什么。我在做什么错？

I first wanted to sum up all of the sumable parts and I expected the result 20( 11 + 9 ) ( even thought the correct answer is 9 ), but I thought it would be a good start. But my code returns number 37 and I have no idea why. What am I doing wrong?

summ = 0

def Opt( n ):
    global summ

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

        return summ

print( Opt( [ 1,2,3 ] ) )

感谢您的时间和

推荐答案

我认为这是您想要的：

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])
0
>>> Opt([1, 2])
3
>>> Opt([2, 3])
5
>>> Opt([1, 2, 3])
9
>>> Opt([1, 2, 3, 4])
19

动态编程大约将大问题划分为小子问题。

Dynamic programming is about dividing the "big problem" into small subproblems.

因此，首先，您应该确定大问题与子问题的关系。您可以通过编写循环关系来实现。在这种情况下：

So, first of all, you should identify how the big problem is related to the subproblems. You do this by writing a recurrence relation. In this case:

Opt(nums) = sum(nums) + min(...)

您还需要一个起点：

Opt(nums) = 0 iff len(nums) == 1

您可以看到，一旦您编写了递归关系，将其转换为Python代码通常非常简单。

As you can see, once you have wrote the recurrence relation, transforming it into Python code is often straightforward.

重要的是要了解每个子问题都是独立的，不需要外部输入。您使用 global 变量不仅会产生错误的结果，而且还违反了动态编程的精神。

It's important to understand that each subproblem is self-contained, and should not need external input. Your use of global variables was not only producing the wrong result, but was against the spirit of dynamic programming.

您使用树来表示 Opt（）很好。您忘记做的是编写每个节点及其子节点之间的关系。如果您这样做了，我几乎可以肯定，您会自己找到正确的解决方案的。

Your use of trees for expressing Opt() is nice. What you forgot to do is writing the relationship between each node and its children. If you did, I'm almost sure that you would have found the correct solution yourself.

我们还没有完成（感谢Stefan Pochmann 引起注意）。为了构建真正的动态编程解决方案，您还需要避免多次解决同一问题。当前，运行 Opt（[1,2,3,4]）会导致调用 Opt（[1,2]）不止一次。一种防止这种情况的方法是使用记忆：

We are not finished yet (thanks Stefan Pochmann for noticing). In order to build a true dynamic programming solution, you also need to avoid solving the same problem more than once. Currently, running Opt([1,2,3,4]) results in calling Opt([1,2]) more than once. One way to prevent that is by using memoization:

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

顺便说一句，请记住处理 n 为空的情况（即 len（n）== 0 ）。

By the way, remember to handle the case where n is empty (i.e. len(n) == 0).

这篇关于动态编程无法给出正确答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！