子集和问题的实例

发布于 2024-12-04 15:41:24 字数 991 浏览 3 评论 0原文

我有一个问题，这是子集总和问题的一个非常清楚的实例：

“给定范围 [-65000,65000] 内的整数列表，如果列表的任何子集总和等于零，则函数返回 true。否则返回 False ”。

我想问的是更多的解释而不是解决方案。

这是我在考虑问题的复杂性之前提出的针对特定实例的解决方案。

对数组 A[] 进行排序，并在排序期间将每个元素求和到计数器 'extSum' (O(NLogN))
定义为指针 low = A[0] 和 high = A[n-1]
以下是决定代码：

while(A[low]<0){
  总和 = extSum;
  如果（extSum>0）{
    while(sum - A[high] < sum){
        tmp = 总和 - A[高]；
        if(tmp==0) 返回真；
        否则如果（tmp>0）{
            总和= tmp；
            高的 - ;
        }
        别的{
            高的 - ;
        }
    }
    extSum -= A[低];
    低++；
    高 = n - 1；
  }
  别的{
    /* 对称代码：切换低电平、高电平以及操作>且< */
  }
}
返回假；

首先，这个解决方案是否正确？我做了一些测试，但我不确定......它看起来太简单了......
这段代码的时间复杂度不是O(n^2)吗？

我已经阅读了各种 DP 解决方案，我想了解的是，对于我面临的问题的具体实例，它们比这种幼稚而直观的解决方案好多少。我知道我的方法可以改进很多，但就时间复杂度而言，没有什么会产生很大的差异......

感谢您的澄清

编辑：一个明显的优化是，而排序，如果找到 0，函数立即返回 true....但这仅适用于数组中有 0 的特定情况。

原文

I have a problem which is a pretty clear instance of the subset sum problem:

"given a list of Integers in the range [-65000,65000], the function returns true if any subset of the list summed is equal to zero. False otherwise."

What I wanted to ask is more of an explanation than a solution.

This was an instance-specific solution I came up before thinking about the complexity of the problem.

Sort the array A[] and, during sort, sum each element to a counter 'extSum' (O(NLogN))
Define to pointers low = A[0] and high = A[n-1]
Here is the deciding code:

while(A[low]<0){
  sum = extSum;
  if(extSum>0){
    while(sum - A[high] < sum){
        tmp = sum - A[high];
        if(tmp==0) return true;
        else if(tmp > 0){
            sum = tmp;
            high--;
        }
        else{
            high--;
        }
    }
    extSum -= A[low];
    low++;
    high = n - 1;
  }
  else{
    /* Symmetric code: switch low, high and the operation > and < */
  }
}
return false;

First of all, is this solution correct? I made some tests, but I am not sure...it looks too easy...
Isn't the time complexity of this code O(n^2)?

I already read the various DP solutions and the thing I would like to understand is, for the specific instance of the problem I am facing, how much better than this naive and intuitive solution they are. I know my approach can be improved a lot but nothing that would make a big difference when it comes to the time complexity....

Thank you for the clarifications

EDIT: One obvious optimization would be that, while sorting, if a 0 is found, the function returns true immediately....but it's only for the specific case in which there are 0s in the array.

分享到QQ

分享到微博