选择点使得x坐标的和等于y坐标的和

Question

我有一个Point数组。我需要从中选择一部分点，使得这些点的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）如果有，可以请任何人解释一下吗？

- xylon97

---

这看起来像是0-1背包问题的变体，因此我相信您只能希望使用DP获得伪多项式解决方案。 - ile

坐标有任何限制吗？例如，它们必须是非负数吗？ - Robin Green

是的，所有坐标都是非负数。您可以假设它们小于10^5。 - xylon97

还有多少点？我们能否在O(n^2 w^2)的时间复杂度内对坐标之和进行DP，其中w是所有x的和。 - ile

@ile：点数小于10^5，所以不可能。 - xylon97

你应该提到它。我认为你不可能很快找到大输入的确切答案。因此，现在可以在下面搜索“背包问题的近似解法”，因为你已经将其归约为子集和问题。 - ile

Answer 1

对于每个点，将其值设置为x-y。

现在我们需要找到一组点，它们的值总和为0。

这正是子集和问题。

它是NP完全问题（即对于问题的通用情况，没有已知的多项式时间算法），但存在一种伪多项式时间DP解决方案，在上面链接的维基百科页面中给出。简要概述如下：

We define a function Q(i,s) to be the value (true or false) of

there is a nonempty subset of x1, ..., xi which sums to s

Then we have the following recurrence:

Q(1,s) := (x1 == s)
Q(i,s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi)   for A ≤ s ≤ B

- Bernhard Barker

Answer 2

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

1. 将所有坐标划分为三个集合：

 1: {(x,y): x>y}, 2: {(x,y):x==y}, 3:{(x,y): x lower-than y}

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

这有意义吗？

- artur grzesiak

---

基本上，这可以简化为众所周知的子集和问题。 - ile

我刚刚通过从Subset-Sum的规约证明了原问题是NP-Hard。看起来这个问题应该被视为Subset-Sum的变体。 - Patricia Shanahan

Answer 3

除非存在未说明的限制条件，否则该问题通过将其多项式时间约化为Subset-Sum问题（一个NP-完全问题）而成为NP难问题。

Subset-Sum问题的决策形式之一是：给定一个整数集合X和一个整数s，是否存在任何非空子集的和等于s。

对于X中的每个元素，构造一个点，其x值为该元素，y值为0。构造一个额外的点，其x值为0，y值为s。

如果将该点集应用于等和问题的结果为0或-1，则拒绝该子集和问题。如果结果为s，则接受该子集和。

假设P != NP，或者至少我们没有任何NP难问题的多项式算法，那么你的问题就没有已知的多项式时间算法。

- Patricia Shanahan

Answer 4

我只是在尝试编写Java代码，我觉得这会很有帮助：

对于所有 i，diffOfCoordinates[i] = Xi - Yi

list 将拥有最大点。

public void fun(int[] diffOfCoordinates, int indexA, int[] b, int indexB, int sum, List<Integer> list){
       if(indexA == diffOfCoordinates.length){
           if(sum==0){
               if(list.size()<indexB){
                   list.clear();
                   for(int i=0;i<indexB;i++){
                       list.add(b[i]);
                   }
               }
           }
           return;
       }
       b[indexB] = diffOfCoordinates[indexA];
       fun(diffOfCoordinates, indexA+1, b, indexB+1, sum+diffOfCoordinates[indexA], list);
       fun(diffOfCoordinates, indexA+1, b, indexB, sum, list);
   }

- Trying