CODEWITHSUNDEEP
algorithm
user3573388
user3573388

Reputation: 191

Dynamic programming solution for 2d subset sum

So i have this problem: given a set of two dimensional tuples on the form {x,y}, where all x and y are positive integers, decide if it is possible to take out a subset so that:

√( (∑x)² + (∑y)²) = A²

For a positive integer A.

Example, given [{2,2},{1,4},{1,2}] and A = 5 one solution is {2,2} and {1,2} since 3² + 4² = 5²

It is allowed to reuse the same tuple multiple times.

The goal is th solve this with dynamic programming. I was looking at http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/, a dynamic solution of a subset sum problem; however the difference here is that all the terms are squared and 2d, so i don't believe that method works

Upvotes: 2

Views: 792

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10565

There may be faster options, but a simple PD is:

T(X, Y, i): Is it possible to achieve the ∑x = X and ∑y = Y using up to the i-th term?

T(0, 0, 0) = TRUE
T(X, Y, i) = FALSE if X<0 or Y<0 or (i==0 and X!=0 and Y!=0)
T(X, Y, i) = T(X-V[i].X, Y-V[i].Y, i) or T(X, Y, i-1)

Then, scan every pair (X, Y), to find one that X²+Y²=A² and T(X, Y, n) is true (where n is the size of the set).

Here is a non-optimized recursive version just to prove the concept (in Python):

def T(V, x, y, i):
    if x==0 and y==0 and i==0: return []
    if x<0 or y<0 or i<=0: return None

    answer = T(V, x-V[i-1][0], y-V[i-1][1], i)
    if answer is not None: return answer + [V[i-1]]
    return T(V, x, y, i-1)

def solve(V, A):
    for x in range(A):
        for y in range(A):
            if x*x+y*y==A*A:
                answer = T(V, x, y, len(V))
                if answer:
                    return answer
    return None

print(solve([(2,2),(1,4),(1,2)], 5))

It prints one possible solution:

[(2, 2), (1, 2)]

Upvotes: 1

Related Questions