2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法

yanmingwuyu · 发表于 2018-7-10 00:32

大神就是大神，只能拿走代码顺便跪地膜拜一下。可是大神能不能加个可以取重复值的开关呢？取重复值的次数不能超过源数据出现的次数。T_T

mythqiu · 发表于 2018-7-12 20:18

确实牛人一个....

神箭 · 发表于 2018-7-16 21:12

功能太强大了！非常感谢香川老师，帮我解决了困扰之久的问题！

goldowl2011 · 发表于 2018-8-18 16:11

香川大侠，无私奉献，技术精湛

15968726522 · 发表于 2018-8-29 11:32

求大神帮忙，四百多个数字有没有办法求出准确解

香川群子 · 发表于 2018-8-29 14:13

15968726522 发表于 2018-8-29 11:32
求大神帮忙，四百多个数字有没有办法求出准确解

5组目标值，凑出2组相同的，1组差1分钱。其余2组误差大一点。

15968726522 · 发表于 2018-8-29 14:49

香川群子发表于 2018-8-29 14:13
5组目标值，凑出2组相同的，1组差1分钱。其余2组误差大一点。

谢谢大神，剩下的我再看看...

香川群子 · 发表于 2018-8-29 16:19

15968726522 发表于 2018-8-29 14:49
谢谢大神，剩下的我再看看...

你是要求把这些数字全部用光，还是取其中的一部分就可以了？

每一个目标金额，相应的取值个数有大致范围吗？（知道这个可以缩短计算时间）

三坛老窖 · 发表于 2018-8-29 17:40

楼上附件中数据，每一个目标和值，存在相当多的精确解，下面是未使用其中负数的每一个目标和值的一组精确解。

5,118,119.21:  2260139.00  700000.00 600000.00 450000.00 310000.00 304465.00 294556.00 197851.08 664.68  315.25  88.20 40.00

4,381,536.21:
1052747.00  800000.00 688600.00 670000.00 421387.50 334398.00 200323.60 197851.08 664.68  660.00  608.00  575.00  565.00  558.00  525.00  520.00  500.00  477.65  450.00  450.00  410.00  402.60  400.00  392.00  383.40  375.00  370.00  367.00  330.00  320.00  315.00  312.00  308.00  300.00  300.00  300.00  300.00  292.00  260.00  246.00  210.00  202.00  192.00  187.50  182.00  180.00  176.00  176.00  170.00  165.00  140.00  126.00  116.00  90.00 88.20 84.00 75.00 70.00 69.00 59.00 54.00 52.00 50.00 40.00 22.00 12.00 5.00

6,274,324.54:
2260139.00  670000.00 600000.00 600000.00 595570.00 421387.50 310000.00 304465.00 294556.00 178000.00 1085.76    1080.00    1064.00    1015.00    1015.00    1000.00    1000.00    1000.00    920.00  910.00  900.00  900.00  892.00  884.00  878.40  864.00  850.00  817.05  816.00  814.00  800.00  800.00  800.00  745.00  744.00  732.00  720.00  664.68  660.00  608.00  575.00  565.00  558.00  525.00  520.00  500.00  477.65  450.00  450.00  410.00  402.60  400.00  392.00  383.40  375.00  370.00  367.00  330.00  320.00  315.00  312.00  308.00  300.00  300.00  300.00  300.00  292.00  260.00  246.00  210.00  202.00  192.00  187.50  182.00  180.00  176.00  176.00  170.00  165.00  140.00  126.00  116.00  90.00 84.00 75.00 70.00 69.00 59.00 54.00 52.00 50.00 40.00 32.00 22.00 5.00

13,482,598.00:
8297105.00  1500000.00  1400000.00  1000000.00  688600.00 595570.00 170.00  165.00  140.00  126.00  116.00  90.00 84.00 75.00 70.00 59.00 54.00 52.00 50.00 40.00 32.00

18,760,134.22:
8297105.00  2708400.00  1100000.00  1052747.00  1000000.00  1000000.00  1000000.00  1000000.00  670000.00 502148.92 421387.50 402.60  392.00  375.00  370.00  367.00  330.00  320.00  315.00  312.00  308.00  300.00  300.00  300.00  300.00  292.00  260.00  246.00  210.00  202.00  192.00  187.50  182.00  180.00  176.00  176.00  170.00  165.00  126.00  116.00  90.00 88.20 84.00 75.00 70.00 69.00 59.00 54.00 52.00 50.00 40.00 22.00 15.50 5.00

香川群子 · 发表于 2018-8-30 12:31

三坛老窖发表于 2018-8-29 17:40
楼上附件中数据，每一个目标和值，存在相当多的精确解，下面是未使用其中负数的每一个目标和值的一组精确解 ...

不考虑负数的话，计算简单多了。

用完全随机算法，可以得到很多精确匹配解，甚至可以同时满足机组：
例如：5,118,119.21

56 个数 2260139+1000000+500000+300000+250000+200000+110200+59600+53928+48000+46523+40000+30000+29837+28193.35+20000+17250+15476+14002+13674+12625+9900+7680+5566+5400+4800+4000+3560+3480+3000+2400+2275+2000+1944.6+1919+1602+1596+1333+1320+1130+1085.76+850+410+320+292+202+176+176+70+69+40+32+22+15.5+12+-6

68 个数 2708400+500000+500000+290000+178000+135000+128240+79950+70729+67608+51107+45000+45000+40000+38950+38449+28000+19709.89+15476+14002+12744+10696+9311+8500+8000+7943+6940.35+6725.59+5523+4760+4360+3490+3480+3418.8+2650.98+2326.7+2275+2247+2000+2000+1920+1684+1680+1300+1130+1080+910+892+800+575+500+383.4+370+330+300+260+246+210+182+126+90+50+40+22+15.5+12+5+-6

48 个数第1组2708400+1000000+500000+200000+150000+126420+60036+50000+44790+40000+38970+36144.5+33000+27624+26946+11575+11455.3+9870.49+7766.25+3514.4+3483.84+3369.77+3065+3000+2842.61+2326.7+1596+1273.2+1130+1103+1015+900+900+892+817.05+816+800+402.6+400+375+370+260+182+140+126+15.5+12+-6
72 个数第2组 1052747+688600+450000+450000+350000+300000+300000+290000+155880+112045+110200+100000+60000+56000+51107+48000+48000+45000+30920+30000+30000+30000+29572.4+27991+27043+20156+19000+18150+16148+14908+14002+13674+13200+9488+9080+8898.7+8040+8000+7943+6940.35+6571.26+5889.6+5040+4800+4368+4172+3997+3011+2286+2000+1944+1920+1666+1597+1312+1200+814+732+608+558+500+477.65+330+315.25+300+300+292+192+116+40+32+5

50 个数第1组 1000000+688600+670000+500000+450000+300000+290000+250000+200000+154322+148413+57032.5+46523+37622+36483+33000+30000+28000+20156+20000+18150+16000+15000+14908+12486+10696+9311+8500+8040+8000+7766.25+6571.26+4442+3710+3065+2343.7+2275+1919+1602+1000+558+450+315+300+202+182+116+50+15.5+-6
57 个数第2组 1000000+800000+502148.92+421387.5+350000+315000+300000+200000+150000+112045+110200+105277.07+76500+72503+53928+50700+45000+43646+40000+33440+32093.8+31200+30000+27991+27624+24966+21391+20762+15476+13351.62+13090+12625+11455.3+8500+8000+5000+4368+4160+3439+3198+3000+2400+2200+1920+1911+1312+1301+1015+800+500+330+300+192+176+165+126+5
86 个数第3组 1400000+500000+310000+300000+220000+197851.08+165000+155880+135000+110573+110432+109758+100000+100000+99000+97828.6+83498+71450+67608+56000+51107+50000+49500+48000+48000+45000+41242+40000+38449+37286+29316+27043+25083+19709.89+19000+17250+13674+12308+9677.2+9112.5+9080+8944+7943+6200+5640.22+4864+4800+4360+3490+3483.84+3369.77+3000+2216.5+1944.6+1935+1684+1666+1596+1472+1385.8+1300+1275.6+1273.2+1085.76+1064+1000+920+910+900+864+850+814+744+732+720+660+565+520+477.65+450+375+300+260+210+84+54

		自动登录	找回密码
密码			免费注册

[原创] 2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法