Динамическое программирование не дает правильного ответа

Question

Недавно я узнал о технике динамического программирования, и я наткнулся на проблему, которую я не могу понять. Сначала вам дается список аргументов, и вам нужно делать суммы, как если бы вы их разрезали. Если список имеет только один элемент, вы не суммируете его. Если в нем больше, вы суммируете элементы и разрезаете их всеми возможными способами. Поэтому, если в списке есть n элементов, существует только n-1 способ разрезать его. Картина объяснит:

я первый хотел подвести итог все sumable частей, и я ожидал, что результат 20 (11 + 9) (даже думал, что правильный ответ 9), но я думал, что это было бы хорошим началом. Но мой код возвращает номер 37, и я понятия не имею, почему. Что я делаю не так?

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 ])) 

Спасибо за ваше время и за любой ответ!

Answer 1

Я думаю, что это то, что вы хотите:

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 

Динамическое программирование о разделении "большие проблемы" на мелкие подзадачи.

Итак, прежде всего, вы должны определить, как большая проблема связана с подзадачами. Вы делаете это, написав рекуррентное отношение. В этом случае:

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

Вы также нужна отправная точка:

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

Как вы можете видеть, как только вы написали рекуррентное соотношение, превращая его в код Python часто просто.

Важно понимать, что каждая подзадача является автономной и не требует внешнего ввода. Ваше использование переменных global не только дало неправильный результат, но и противоречило динамическому программированию.

Ваше использование деревьев для выражения Opt() приятно. То, что вы забыли сделать, это написать отношения между каждым узлом и его дочерними элементами. Если бы вы это сделали, я почти уверен, что вы нашли бы правильное решение самостоятельно.

Мы еще не закончили (спасибо Stefan Pochmann за то, что заметили). Чтобы создать истинное решение динамического программирования, вам также необходимо избегать решения одной и той же проблемы более одного раза. В настоящее время работает Opt([1,2,3,4]) приводит к вызову Opt([1,2]) более одного раза. Один из способов предотвратить это с помощью запоминания:

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).