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