Problemy z programowaniem dynamicznym

Question

Mam trudności ze zrozumieniem programowania dynamicznego, więc postanowiłem rozwiązać niektóre problemy. Znam podstawowe algorytmy dynamiczne, takie jak najdłuższy wspólny podciąg, problem plecakowy, ale znam je, ponieważ je czytam, ale nie mogę wymyślić czegoś na własną rękę :-(

Na przykład mamy podsekwencję liczb naturalnych. każdy numer możemy zabrać ze sobą plus lub minus na koniec bierzemy wartość bezwzględną tej sumy na każdy podciąg znaleźć najniższą możliwą wynik

IN1:... 10 3 5 4; OUT1: 2

IN2 : 4 11 5 5 5; out2: 0

in3: 10 50 60 65 90 100; out3: 5

wyjaśnienie dla 3: 5 = | 10 + 50 + 60 + 65-90-100 |

Co gorsza, mój przyjaciel powiedział mi, że jest to prosty problem z plecakiem, ale nie widzę tutaj żadnego plecaka. Czy programowanie dynamiczne jest trudne, czy tylko mam z tym duże problemy?

Answer 1

Jak wskazał amit, ten algorytm można rozumieć jako instancję modelu partition problem. Dla prostego wdrożenia spojrzeć na tym kodzie Pythona:

def partition(A): 
    n = len(A) 
    if n == 0: 
     return 0 
    k, s = max(A), sum(A)/2.0 
    table = [0 if x else 1 for x in xrange(n*k)] 
    for i in xrange(n): 
     for j in xrange(n*k-1, -1, -1): 
      if table[j-A[i]] > table[j]: 
       table[j] = 1 
    minVal, minIdx = float('+inf'), -1 
    for j in xrange(int(s)+1): 
     if table[j] and s-j < minVal: 
      minVal, minIdx = s-j, j 
    return int(2*minVal) 

Wywołane z jednym z wejść na pytanie:

partition([10, 50, 60, 65, 90, 100]) 

on powróci 5, jak oczekiwano. Aby w pełni zrozumieć matematykę stojącą za rozwiązaniem, spójrz na tę examples i kliknij link "Balanced Partition".

Answer 2

To jest ten sam problem co w przeciąganie liny, bez przymusu zrównoważonych rozmiarów zespołu (co nie jest istotne): http://acm.uva.es/p/v100/10032.html

miałem rozwiązać ten problem z podejściem odgórnym. Działa na ograniczeniu, że istnieje górny limit podanych liczb. Czy masz górny limit, czy też liczby są nieograniczone? Jeśli są nieskrępowane, nie widzę sposobu rozwiązania tego problemu przy programowaniu dynamicznym.

Answer 3

Opaska na plecaki w tym miejscu to weight = value = number dla każdego elementu.

Twój związany W to 1/2 * sum(elements).

Pomysł polega na tym, że chcesz zmaksymalizować ilość liczb, które wybierasz, nie przekraczając limitu 1/2 * sum(elements), czyli dokładnie plecaka z value=weight.

Ten problem dotyczy w rzeczywistości partition problem, który jest szczególnym przypadkiem urządzenia subset sum problem.

Problem z partycją brzmi: "Czy możliwe jest uzyskanie podzbioru elementów, które sumują się dokładnie do połowy?" Pochodzenie twojego problemu jest proste - jeśli tak, to weź je jako +, a te, których nie wziąłeś jako -, otrzymasz out = 0. [na odwrót działa tak samo]. W związku z tym opisywany problem polega na optymalizacji problemu z partycją.