选择点,使得x坐标的总和= y坐标的总和

Question

我有一系列的Points.我需要从中选择一个点子集,这样点的x坐标之和=点的y坐标之和.如果存在许多这样的子集,则需要具有最大x坐标总和的子集.需要报告x坐标的总和.

我写了一个强力递归方法,测试所有可能性.

Point[] a = new Point[n];
// ...
private int rec(int i, int x, int y) {
    if (i == n - 1) {
        if (x + a[i].x == y + a[i].y) return x + a[i].x;
        return (x == y) ? x : -1;
    }
    return Math.max(rec(i + 1, x, y), rec(i + 1, x + a[i].x, y + a[i].y));
}

答案是rec(0, 0, 0).

我的问题是:

1)有没有动态编程解决方案？
2)如果是,可以请任何人解释

Answer 1

我有一个更好的（比暴力）算法。

1. 将所有坐标分为三组：

   1: {(x,y): x>y}, 2: {(x,y):x==y}, 3:{(x,y): x 低于 y}

2. 集合2必须始终包含在解决方案中。
3. 1对于定义中的每个 (x,y)net=x-y和对于每个 (x,y) 形式3定义net=y-x
4. 检查可以从nets in1和nets in获得的所有可能值3。
5. 然后根据最大匹配很容易构建解决方案。

是否有意义？