algorithm - 二维子集和的动态规划求解

Question

所以我有这个问题:给定一组 {x,y} 形式的二维元组，其中所有 x 和 y 都是正整数，决定是否可以取出一个子集，以便:

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

对于正整数A。

例子，给出[{2,2},{1,4},{1,2}] 和 A = 5一种解决方案是 {2,2} 和 {1,2} 因为 3² + 4² = 5²

允许多次重复使用同一个元组。

目标是用动态规划解决这个问题。我在看http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ , 子集求和问题的动态解；但是这里的区别在于所有项都是平方和 2d，所以我不认为该方法有效

Answer 1

可能有更快的选择，但一个简单的 PD 是:

T(X, Y, i):是否可以使用第 i 项来实现 ∑x = X 和 ∑y = Y？

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)

然后，扫描每一对 (X, Y)，找到 X²+Y²=A² 和 T(X, Y, n) 为真的一对(其中 n 是集合的大小)。

这里是一个非优化的递归版本，只是为了证明这个概念(在 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))

它打印出一种可能的解决方案:

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