Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Problems with dynamic programming

I've got difficulties with understanding dynamic programming, so I decided to solve some problems. I know basic dynamic algorithms like longest common subsequence, knapsack problem, but I know them because I read them, but I can't come up with something on my own :-(

For example we have subsequence of natural numbers. Every number we can take with plus or minus. At the end we take absolute value of this sum. For every subsequence find the lowest possible result.

in1: 10 3 5 4; out1: 2

in2: 4 11 5 5 5; out2: 0

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

explanation for 3rd: 5 = |10+50+60+65-90-100|

what it worse my friend told me that it is simple knapsack problem, but I can't see any knapsack here. Is dynamic programming something difficult or only I have big problems with it?

like image 943
xan Avatar asked Mar 25 '12 17:03

xan


People also ask

What are the drawbacks of dynamic programming?

Disadvantages of Dynamic Programming over recursionIt takes a lot of memory to store the calculated result of every subproblem without ensuring if the stored value will be utilized or not. Many times, output value gets stored and never gets utilized in the next subproblems while execution.

Which problems Cannot be solved by dynamic programming?

9. Which of the following problems is NOT solved using dynamic programming? Explanation: The fractional knapsack problem is solved using a greedy algorithm.

Why is dynamic programming difficult?

Dynamic programming (DP) is as hard as it is counterintuitive. Most of us learn by looking for patterns among different problems. But with dynamic programming, it can be really hard to actually find the similarities. Even though the problems all use the same technique, they look completely different.

Can any problem be solved with dynamic programming?

So, dynamic programming is not a solution for all problems. The two dynamic programming properties which can tell whether it can solve the given problem or not are: Optimal substructure: An optimal solution to a problem contains optimal solutions to sub problems.


1 Answers

As has been pointed out by amit, this algorithm can be understood as an instance of the partition problem. For a simple implementation take a look at this Python code:

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)

When called with one of the inputs in the question:

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

It will return 5, as expected. For fully understanding the math behind the solution, please take a look at this examples and click the "Balanced Partition" link.

like image 124
Óscar López Avatar answered Dec 01 '22 07:12

Óscar López