CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problempartition-problem
xan
xan

Reputation: 1053

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?

Upvotes: 7

Views: 5121

Answers (3)

Óscar López
Óscar López

Reputation: 236170

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.

Upvotes: 5

amit
amit

Reputation: 178531

The knapsack in here is weight = value = number for each element.

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

The idea is - you want to maximize the amount of numbers you "pick" without passing the limit of 1/2 * sum(elements), which is exactly knapsack with value=weight.

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

The partition problem says: "Is it possible to get a subset of the elements that sums exactly to half?"
The derivation to your problem from here is simple - if there is, take these as +, and those you didn't take as -, and you get out = 0. [the other way around works the same]. Thus, your described problem is the optimization for partition problem.

Upvotes: 2

ypnos
ypnos

Reputation: 52417

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

I had solved this problem with a top-down approach. It works on the constraint that there is an upper limit to the numbers given. Do you have an upper limit or are the numbers unconstrained? If they are unconstrained I don't see how to solve this with dynamic programming.

Upvotes: 0

Related Questions