数学研发论坛

 找回密码
 欢迎注册
查看: 340|回复: 6

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

[复制链接]
发表于 2020-2-1 21:36:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 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).
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-1 21:52:50 | 显示全部楼层
没记错是NPC问题
直接找近似解吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-1 22:30:40 | 显示全部楼层
本帖最后由 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、{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的情况,那么此时就可判断不存在,终止程序。


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-1 22:46:42 | 显示全部楼层
本帖最后由 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问题一样,不会死循环。

复杂度也不知如何计算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-2 09:34:48 | 显示全部楼层
本帖最后由 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),再进行判断。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-2 09:46:28 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-2-2 09:52 编辑

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

补充内容 (2020-2-2 22:33):
还要考虑是否存在向左移过程中又跑到尾部去了这种情况。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-2 10:18:47 来自手机 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-2-2 12:11 编辑
aimisiyou  2020-2-1 22:46

1Vlstlisti()
2listi ...


对于第1条,可以看成在一个封闭的系统里不停变换状态(最多n!个状态),一定会出现list相同的情况。既不会出现死循环。
对于第2条,a1的位置不好判断,有时移到尾部(数列较短时),有时向前移动(数列较长时)。即判断结果为不存在的正确性需要理论证明。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-4-8 09:09 , Processed in 0.051100 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表