凑数程序（WPS-JS版本）

wodewan

一执成念 发表于 2023-1-12 11:23
老板，来个vba版的

大佬有要求必须安排，已经发了，在审核，还请多多指教。。。

一执成念

wodewan 发表于 2023-1-12 15:50
大佬有要求必须安排，已经发了，在审核，还请多多指教。。。

你才是真大佬

jz_l

wodewan 发表于 2023-1-12 15:40
哈哈，好啊，JSA看不懂没关系，凑数主要是个逻辑，学习不敢当，还请多指教。难得2位大佬有兴趣，既然这样 ...

数据不多时倒无所谓，数据多了，有没有剪枝优化差别还是非常大的

wodewan

jz_l 发表于 2023-1-13 16:25
数据不多时倒无所谓，数据多了，有没有剪枝优化差别还是非常大的

哈哈，好久不见，感谢回复，是这样的，剪枝优化是很重要的。

因为数据是有序的，目前能想到的也就是在组合的过程中下一个元素的值如果比剩余值大，那这条分支就可以剪枝了，代码就只加了这一条剪枝操作。



也想了一些其他剪枝方法，但好像都被这一条所包含了，另外对负数的处理除了倒叙也没想到什么特别好的方法，如果有啥好的处理剪枝和负数的方法，还望能指点一二，多谢！

xinyun724

强大，值得学习

jz_l

wodewan 发表于 2023-1-13 16:48
哈哈，好久不见，感谢回复，是这样的，剪枝优化是很重要的。

因为数据是有序的，目前能想到的也就是在 ...

那我就说两句吧
以有序整数1,2,3,4,...,19,20（以下简称：源数据），凑和为30为例：
1、源数据最后几个数中，19+20=39，>=30，所以结果至少是2个数的组合。
2、源数据最前几个数中，1+2+...+7=28<30，而1+2+...+7+8=36>=36，所以结果至多是7个数的组合。
3、剪头：
如计算取3个数和为30，
若第1个数取1，因源数据最大为20，则第2个数至少要从30-20-1=9开始，即第2个数跳过2-8。
4、剪尾：
如计算取4个数和为30，
若第1、第2个数分别取5、6，5+6=11，剩余第3、第4这2个数之和为30-11=19，则第3个数至多取到9（9-10=19），跳过10之后的数。

很久以前写的凑整数的
https://club.excelhome.net/forum ... 71&pid=11005033

wodewan

jz_l 发表于 2023-1-13 17:30
那我就说两句吧
以有序整数1,2,3,4,...,19,20（以下简称：源数据），凑和为30为例：
1、源数据最后几个 ...

好的，好的，感谢这么快回复，我好好拜读一下，多谢！！！

micch

主体就这么一点代码，但是看的还是不懂，果然凑数不适合我。




看过很多凑数的代码，这个搜索思路总是理解不了

huanghai22

这组数据你的VBA代码卡死，WPS版（没测试，没安装WPS）

wodewan

huanghai22 发表于 2023-1-13 20:00
这组数据你的VBA代码卡死，WPS版（没测试，没安装WPS）

看来这个帖子没白发，看到你的回复说实在的挺意外的，没怎么学过数据结构和算法，之前也没写过凑数程序，对凑数里面的逻辑其实一窍不通，只是一个爱好者，写这个兴趣还是来自前两天刷到你的那个挑战贴，很好奇你是怎么做到的？还和一个群友讨论了一下，于是也想试一下，就用JS先按正常的组合套路写了个，开始是递归写的，后来用你帖子里那个10万的数据源，也就是这个帖子演示的那个例子，发现递归会溢出，就想着改个循环，竟然七拼八凑的改出来了，也不溢出了，并且针对那个数据集效率还很高，当时还有点小得瑟，，你应该看到了我在你帖子里的回复了。


不过后来，慢慢发现，并没那么简单，不同的数据集应该是有不同的处理方式的，想要做到均衡，没那么简单。我知道一说凑数肯定是个热门的话题，与其一知半解，还不如把代码贴出来，找点存在感，等各路大神的指正，还能从中白嫖不少知识，于是就有了这个贴子，是不是有点，哈哈。。。
所以你说那个程序卡死，一点都不意外，只有10多行JS的代码能做到通用才奇怪了，自己都不信，让你见笑了。。。

但这个过程还是挺好玩，挺有意思的，仅此而已，虽然只是众多【凑数程序】中“凑数”的，但因为爱好，所以“凑数”，无论凑出是几。。。