Problems with dynamic programming

Question

I had difficulty understanding dynamic programming, so I decided to solve some problems. I know the basic dynamic algorithms, such as the longest common subsequence, the problem with the backpack, but I know them because I read them, but I can not come up with something on my own :-(

For example, we have a subsequence of natural numbers. Every number that we can take with a plus or minus. In the end, we accept the absolute value of this amount. For each subsequence, we find the smallest 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 the 3rd: 5 = | 10 + 50 + 60 + 65-90-100 |

The worse my friend told me that this is a simple backpack problem, but I don’t see any backpack here. Is dynamic programming something difficult or only I have big problems with it?

Answer 1

As amit noted, this algorithm can be understood as an instance of a 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[jA[i]] > table[j]: table[j] = 1 minVal, minIdx = float('+inf'), -1 for j in xrange(int(s)+1): if table[j] and sj < minVal: minVal, minIdx = sj, j return int(2*minVal) 

When called with one of the inputs in the question:

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

He will return 5 , as expected. To fully understand the math behind the solution, check out these examples and click on the Balanced Separation link.

Answer 2

The backpack here is weight = value = number for each item.

your bound W is 1/2 * sum(elements) .

The idea is that you want to maximize the number of numbers that you "select" without going over the 1/2 * sum(elements) limit, which is exactly a backpack with value=weight .

This problem is actually a problem, which is a special case of the problem of a subset of sums .

The problem with the section is: "Is it possible to get a subset of the elements that make up exactly half?"
The conclusion to your problem from here is simple - if there is, take them as + , and those that you did not take for - , and get out = 0 . [vice versa works the same way]. So your described problem is optimizing the partition problem.

Answer 3

This is the same problem as in Tug Of War, without limiting the balanced size of the team (which is not relevant): http://acm.uva.es/p/v100/10032.html

I solved this problem with a top-down approach. He is working on the limitation that there is an upper limit to the number. Do you have an upper limit or unlimited numbers? If they are not limited, I do not see how this can be solved using dynamic programming.