判断数列里是否存在某几个数的和值为K

aimisiyou

如何快速判断一列数里是否存在某几个数相加的和值为确定值K？
如数列为{27,15,13,9,6,4,1}，K=35。只讨论算法判断过程。


补充内容 (2020-2-2 11:17):
若选取为1，不选取为0，即从（0,0,0,0,0,0,0）到（1,1,1,1,1,1,1）进行判断，复杂度为O(2^n).

.·.·.

没记错是NPC问题
直接找近似解吧

aimisiyou

我先说说我的算法吧。先将数列由大到小排序，令vlst=nil.
1、令sum=0，然后从第一个数开始，若sum=sum+ai<=K,则计入ai,否则不计入，一遍走完后会得到一个和值不大于K的子列表lst1,将lst1放入vlst,同时将lst1放在原数列尾部；
2、重复1过程。
判断准则1、若某个lsti和值为K，则可判断存在；2、若重复了n次，Vlst={lis1，list2…listi…listn}，仍没有和值为K的list,但再多走一步，出现的listj在vlst中出现过，即可判断不存在。

1、{27  15  13   9  6  4  1}={15  13   9   4   27   6   1}     vlst={{27   6  1}}
2、{15  13   9   4   27 6 1} ={9   27   6   15  13   4   1}    vlst={{27   6  1} {15   13   4  1}  }
3、{9   27   6   15  13   4   1} ={27  13   9  6   15   4   1}    vlst={{27   6  1} {15   13   4  1} {9   6   15  4  1} }  此时{9   6   15  4  1}满足要求及存在。此时可以终止程序，但为了说明算法，继续往下验算。
4、{27  13   9  6   15   4   1}={13   9  15    4  27  6  1}    vlst={{27   6  1} {15   13   4  1} {9   6   15  4  1} {27   6  1} } 而  {27   6  1} 在前面出现过，假设前面不存在和值为K的情况，那么此时就可判断不存在，终止程序。

aimisiyou

前提有两点需要证明：
1、不断重复下去，Vlst中一定会出现相同的listi(排好序后再比较)；
2、两相同listi之间若不存在和值为K的list,之后也一定不存在和值为K的list.（类似转了一圈都不存在）


循环的条件为

{while   （list和值不为K   or    list不在vlst中出现过）

  循环操作1和2；

}


不知这个循环条件  是否和3X+1问题一样，不会死循环。

复杂度也不知如何计算。

aimisiyou

上述是在无重复数字的情况下。若ai重复ki个，则只保留min{K/ai,ki}个ai，组成的数列再排序，进行运算。如判断（27，27，15，15，15，13，13，13，9，9，9，9，6，6，6，6，6，6，4，4，1，1，1）是否存在和值为35的组合，则先将列表预处理成（27，15，15，13，13，9，9，9，6，6，6，6，6，4，4，1，1，1），再进行判断。

aimisiyou

如果预处理完后的列表长度为n,则时间复杂度应该小于O(n^2)，因为假想最坏情况每次只移一位到列表最后，每次移动前要进行n次判断运算。

补充内容 (2020-2-2 22:33):
还要考虑是否存在向左移过程中又跑到尾部去了这种情况。

aimisiyou

aimisiyou  2020-2-1 22:46

1Vlstlisti()
2listi ...

对于第1条，可以看成在一个封闭的系统里不停变换状态（最多n!个状态），一定会出现list相同的情况。既不会出现死循环。
对于第2条，a1的位置不好判断，有时移到尾部（数列较短时），有时向前移动（数列较长时）。即判断结果为不存在的正确性需要理论证明。