判断数列里是否存在某几个数的和值为K
本帖最后由 aimisiyou 于 2020-2-1 21:39 编辑如何快速判断一列数里是否存在某几个数相加的和值为确定值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 于 2020-2-1 22:38 编辑
我先说说我的算法吧。先将数列由大到小排序，令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、{271513 9641}={1513 9 4 27 6 1} vlst={{27 61}}
2、{1513 9 4 27 6 1} ={9 27 6 1513 4 1} vlst={{27 61} {15 13 41}}
3、{9 27 6 1513 4 1} ={2713 96 15 4 1} vlst={{27 61} {15 13 41} {9 6 1541} }此时{9 6 1541}满足要求及存在。此时可以终止程序，但为了说明算法，继续往下验算。
4、{2713 96 15 4 1}={13 915 42761} vlst={{27 61} {15 13 41} {9 6 1541} {27 61} } 而{27 61} 在前面出现过，假设前面不存在和值为K的情况，那么此时就可判断不存在，终止程序。
本帖最后由 aimisiyou 于 2020-2-2 01:01 编辑
前提有两点需要证明：
1、不断重复下去，Vlst中一定会出现相同的listi(排好序后再比较)；
2、两相同listi之间若不存在和值为K的list,之后也一定不存在和值为K的list.（类似转了一圈都不存在）
循环的条件为
{while （list和值不为K or list不在vlst中出现过）
循环操作1和2；
}
不知这个循环条件是否和3X+1问题一样，不会死循环。
复杂度也不知如何计算。 本帖最后由 aimisiyou 于 2020-2-2 09:39 编辑
上述是在无重复数字的情况下。若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 于 2020-2-2 09:52 编辑
如果预处理完后的列表长度为n,则时间复杂度应该小于O(n^2)，因为假想最坏情况每次只移一位到列表最后，每次移动前要进行n次判断运算。
补充内容 (2020-2-2 22:33):
还要考虑是否存在向左移过程中又跑到尾部去了这种情况。 本帖最后由 aimisiyou 于 2020-2-2 12:11 编辑
aimisiyou2020-2-1 22:46
1Vlstlisti()
2listi ...
对于第1条，可以看成在一个封闭的系统里不停变换状态（最多n!个状态），一定会出现list相同的情况。既不会出现死循环。
对于第2条，a1的位置不好判断，有时移到尾部（数列较短时），有时向前移动（数列较长时）。即判断结果为不存在的正确性需要理论证明。
页:
[1]