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

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

6274324.54

64 1400000+1052747+800000+500000+350000+300000+300000+250000+200000+200000+141140+110200+100000+60000+53928+53500+51107+50000+45000+30000+27991+24000+20000+16896.8+16484+15100+12746+11008.72+9900+7999.38+7943+7766.25+5849+4864+4760+4360+4172+3952+3381+2846+2650.98+1680+1590+1410+1112+1085.76+745+608+575+500+477.65+450+410+367+320+176+176+116+84+70+69+12+5+-6

91 1000000+1000000+700000+670000+600000+450000+250000+200000+153000+128240+112045+109758+100000+83498+50000+48000+46523+45000+40000+40000+38970+36483+30000+30000+30000+29455+26946+24966+21867+20282+20000+18150+15000+11455.3+9870.49+8000+6500+5420+5040+4368+4160+3698.42+3490+3483.84+3348+3065+2842.61+2670+2051+2000+2000+2000+1911+1590+1385.8+1300+1200+1112+1064+1015+910+884+817.05+745+664.68+660+608+565+525+500+477.65+450+367+312+308+300+192+182+126+90+88.2+84+59+54+52+32+22+15.5+12+5+-6
99 800000+500000+500000+500000+350000+320000+315000+300000+290000+220000+200000+197851.08+154322+150000+141140+126420+124286+105000+100000+60000+57032.5+51200+41344.8+41242+38950+34960+33000+32093.8+31488+30000+28881+28000+24000+24000+20762+20625+20156+17250+16000+14908+13200+12900+12746+12744+12095+10325.7+9457+8944+8040+8000+7999.38+7983.91+6725.59+6571.26+5889.6+5640.22+5566+5036+4360+4172+3710+3480+3300+3011+2286+2250+2216.5+1944+1935+1919+1597+1472+1320+1312+1301+1275.6+1080+1015+1000+1000+1000+900+892+720+575+520+450+402.6+400+330+300+246+180+176+176+140+75+70+40

73 1000000+1000000+800000+670000+450000+400000+294556+200323.6+154322+153000+148413+113010+110432+110200+100000+100000+60036+50000+49500+48000+28000+27624+27043+20156+15476+14653.84+12308+9112.5+8500+8322+8000+7999.38+7983.91+6829.76+6725.59+5849+3952+3490+3480+3381+3369.77+3000+2842.61+2650.98+2557+2326.7+2250+2247+2000+1597+1596+1320+1000+745+477.65+450+400+392+370+330+320+315.25+260+246+202+84+75+54+52+50+40+32+-6
60 1400000+1000000+1000000+600000+450000+350000+250000+128240+110573+109758+105000+83498+70729+53488+50000+45000+41344.8+40000+37622+30920+30000+29837+29572.4+29455+29316+25083+24000+24000+11575+11008.72+10563+9900+9311+6500+4760+4442+4368+3483.84+3439+3348+3300+2051+1015+1000+920+910+878.4+864+664.68+520+450+410+375+300+192+165+88.2+59+15.5+12

48 1052747+1000000+1000000+700000+700000+500000+500000+421387.5+141140+56000+50700+37622+27043+15476+15100+8944+6571.26+5523+4864+4760+3514.4+3480+3348+2343.7+2275+1935+1602+1301+1275.6+850+664.68+660+565+392+383.4+320+312+300+202+180+176+165+54+52+50+40+12+-6
75 2708400+502148.92+300000+294556+290000+220000+200000+126420+113010+112045+109758+105034+100000+97828.6+79950+67608+50000+44790+40000+40000+37978.94+37286+36483+36144.5+31200+30000+30000+29316+28000+27991+26946+26295+24966+24000+21867+21391+19709.89+18807+16148+15000+12744+12308+11008.72+8898.7+8322+8000+7983.91+7680+6940.35+5640.22+5420+5036+3710+3381+3065+2842.61+2650.98+2612.8+2250+2100+2051+1597+1596+1472+884+800+520+477.65+450+315.25+246+126+70+32+15.5
58 1400000+1000000+600000+500000+450000+400000+400000+200000+155880+154322+150000+83498+72503+60000+53500+51107+45000+45000+40000+40000+38970+38950+34960+33440+24000+20625+19909+19009.94+18150+16484+15000+14653.84+10000+8500+8500+8040+6829.76+6500+4368+3480+3439+3300+3000+2670+2200+2000+1919+1320+1112+558+525+300+300+192+140+90+75+5
70 1000000+1000000+670000+450000+450000+320000+310000+300000+200000+200000+148413+110573+110432+100000+100000+99000+71450+50000+50000+48000+48000+45000+41344.8+33000+30920+30000+27624+20156+20000+19000+18760+16896.8+16315.6+14121+13674+12621+11575+9457+8000+8000+5566+3952+3483.84+3198+2557+2286+2000+2000+1944+1911+1680+1410+1385.8+1333+1200+1015+1000+892+745+575+370+315+260+210+187.5+176+170+88.2+59+22

上面这个表明可以同时凑满4组。

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

18760134.22

112 8000000+1400000+1000000+1000000+1000000+1000000+600000+595570+500000+400000+315000+200323.6+200000+200000+200000+197851.08+178000+150000+135000+124286+110573+105277.07+100000+79950+72503+70729+53928+51333+46523+45000+41344.8+38950+31488+29837+29572.4+29455+27043+24000+21867+20762+20282+19909+18807+17250+16484+15100+14653.84+13674+13351.62+12900+12625+11575+9677.2+9311+8500+8000+8000+8000+7943+6940.35+6725.59+5640.22+5523+4368+3952+3560+3490+3483.84+3480+2846+2842.61+2557+2400+2326.7+2200+2160+2000+2000+1385.8+1320+1301+1130+1112+1080+1015+920+910+900+816+814+800+744+720+565+558+520+450+402.6+383.4+367+308+246+210+176+126+52+50+22+15.5+12+5+-6

204 2708400+1100000+1000000+1000000+1000000+1000000+1000000+700000+595570+500000+500000+450000+400000+334398+300000+300000+300000+294556+290000+250000+250000+200000+197851.08+165000+155880+154322+153000+150000+140718+135000+110573+109758+103920+100000+100000+100000+97828.6+83498+79950+76500+71450+70729+59600+57032.5+53928+51333+50700+50000+49500+46523+45000+45000+44790+41242+40000+40000+38970+37286+36483+34960+31200+30920+30000+30000+30000+29837+29572.4+29316+28881+28193.35+27991+27624+26946+26295+24966+24000+24000+21391+20625+20156+20000+19709.89+19000+18760+18150+17250+16896.8+16484+16315.6+16000+15476+14908+14121+13090+12900+12746+12744+12621+11008.72+10696+10325.7+10000+9870.49+9677.2+9457+9311+9112.5+8500+7983.91+7680+6940.35+6200+5889.6+5849+5566+5496.58+5400+5040+4864+4800+4368+4360+4172+4160+3710+3514.4+3483.84+3418.8+3300+3065+3011+3000+3000+2846+2650.98+2400+2250+2247+2200+2051+2000+2000+1935+1920+1919+1684+1666+1602+1597+1472+1410+1385.8+1320+1300+1275.6+1200+1130+1112+1103+1015+1000+1000+910+884+850+816+800+800+745+744+720+664.68+575+520+500+477.65+450+410+400+392+367+308+300+246+202+192+187.5+180+176+170+165+140+126+116+88.2+84+50+40+32+22+15.5+12+5+-6

135 8000000+1500000+1000000+1000000+1000000+800000+595570+450000+421387.5+300000+300000+294556+250000+200000+197851.08+150000+135000+125982+112045+110432+110200+105000+100000+97828.6+83498+79950+56000+53500+51333+50000+50000+45000+40000+40000+38970+38781.8+38449+36483+36144.5+31200+30000+29572.4+29455+29316+27043+26946+21867+21391+20762+19909+19709.89+18807+16315.6+16148+16000+15000+14002+12900+12746+12308+12095+11575+10000+9870.49+9677.2+9457+9112.5+8944+8898.7+8500+8322+8000+7983.91+6940.35+6725.59+6571.26+5523+4800+4442+4360+4172+3710+3514.4+3198+3000+3000+2846+2670+2612.8+2286+2000+1935+1680+1666+1596+1410+1301+1200+1130+1112+1103+1015+1000+1000+910+878.4+850+816+814+800+800+745+720+575+520+477.65+450+392+383.4+330+315+300+300+246+210+192+180+176+88.2+84+75+70+50+40+32

这个因为总额大，所以满足条件的组合少一点。

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

4381536.21

58 1000000+670000+600000+315000+310000+250000+200000+197851.08+83498+76500+67608+51200+50700+46523+38950+37978.94+37286+33000+30000+29455+29316+26295+25083+24966+20000+14002+13674+12746+12625+12486+10563+8500+8000+6725.59+6200+3418.8+3381+2160+2000+1919+1684+1590+1472+1301+1275.6+1000+1000+800+558+370+308+176+90+88.2+69+54+50+40

65 2260139+450000+320000+155880+135000+126420+125982+105277.07+83498+70729+59600+48000+45000+44790+33000+32093.8+31200+30920+30000+28193.35+26946+24000+12746+12308+10000+9311+8322+8000+6940.35+5000+4000+3348+3011+3000+2650.98+2612.8+2400+2286+2275+2216.5+2160+1944+1680+1273.2+1085.76+884+800+565+520+477.65+450+450+392+315.25+300+300+260+165+116+84+70+69+59+15.5+5
65 1000000+502148.92+500000+450000+450000+334398+220000+110432+105034+105000+100000+45000+43646+40000+37978.94+30000+29572.4+29455+27991+27624+20282+19909+18807+16484+16000+10325.7+9900+9488+8898.7+6829.76+5640.22+4368+3560+3490+3480+3480+3418.8+3369.77+3198+2100+2000+1911+1666+1596+1320+1200+1130+1130+1112+1015+1000+920+900+900+575+525+410+400+210+126+75+40+32+22+12

55 1000000+700000+500000+450000+300000+290000+220000+141140+113010+79950+59600+57032.5+56000+51333+44790+40000+34960+33440+30000+21391+20625+20000+18760+15100+14121+14002+8898.7+7983.91+5889.6+5400+5036+5000+3381+2247+2000+2000+1596+1410+1015+884+565+525+450+315+300+210+202+187.5+182+180+170+165+90+5+-6
81 500000+500000+400000+350000+300000+294556+200000+197851.08+150000+126420+124286+112045+110200+105277.07+100000+99000+76500+53928+48000+41242+40000+37286+33800+30000+30000+29572.4+28000+26946+24000+20156+20000+18807+16896.8+16000+15000+12744+12095+11455.3+9311+8322+7999.38+5523+4360+3698.42+3514.4+3000+3000+2051+1684+1680+1590+1301+1112+1103+1085.76+1080+1000+1000+878.4+800+744+575+375+370+367+292+260+246+192+176+140+126+88.2+84+70+69+59+52+50+32+12
74 1000000+688600+421387.5+304465+300000+250000+200323.6+200000+150000+110573+60000+50000+45000+45000+41344.8+40000+40000+38449+37336.1+32093.8+29837+28193.35+21867+20762+19909+19009.94+16148+16000+14653.84+13090+12486+10563+7943+7680+6940.35+6829.76+6725.59+6571.26+5496.58+5420+5040+4368+3710+3483.84+3439+3300+2670+2557+2343.7+2326.7+2200+1597+1472+1312+1273.2+1200+910+900+817.05+816+745+720+520+410+402.6+392+383.4+315.25+300+300+300+176+116+22

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

13482598

205 1052747+1000000+1000000+700000+670000+500000+450000+450000+350000+315000+300000+300000+300000+250000+250000+200323.6+200000+200000+200000+197851.08+165000+155880+154322+153000+148413+135000+126420+125982+124286+112045+110573+109758+105277.07+103920+100000+100000+100000+99000+97828.6+79950+76500+70729+67608+60000+59600+57032.5+53928+53488+51200+50700+50000+50000+50000+49500+48000+45000+45000+44790+43646+41242+40000+40000+38781.8+38449+37978.94+37286+33440+33000+31200+30920+30000+30000+29455+28193.35+28000+27624+21867+21391+20625+20156+19909+19709.89+19000+18807+16315.6+16148+14653.84+14002+13200+13090+12900+12744+12621+12486+12095+11575+11455.3+9677.2+9311+9112.5+9080+8944+8898.7+8000+8000+7999.38+7983.91+7680+6829.76+6571.26+6500+5523+5496.58+4864+4800+4368+4172+3997+3952+3710+3560+3490+3483.84+3480+3480+3439+3300+3065+3011+3000+3000+2846+2842.61+2612.8+2400+2326.7+2275+2000+2000+2000+1935+1919+1911+1472+1410+1333+1312+1301+1300+1273.2+1130+1085.76+1080+1064+1015+1000+920+910+900+892+884+878.4+864+850+800+744+732+664.68+565+525+477.65+450+402.6+400+392+383.4+367+330+320+312+300+300+300+300+292+260+246+180+176+176+170+140+90+84+75+59+54+52+50+40+22+15.5+12+5+-6

60 8297105+1000000+1000000+1000000+500000+450000+300000+200323.6+178000+135000+67608+40000+31200+30000+30000+29572.4+26946+20625+19009.94+18150+16484+16000+13200+10000+9311+5849+4760+3698.42+3369.77+2842.61+2216.5+2200+2000+2000+1944.6+1911+1597+1410+1301+1200+1085.76+910+732+450+383.4+330+315+300+300+192+170+165+126+116+75+70+32+12+5+-6
134 1500000+1100000+1000000+1000000+800000+700000+502148.92+500000+450000+450000+400000+350000+320000+304465+300000+300000+250000+250000+200000+200000+154322+153000+150000+126420+124286+113010+110573+110200+109758+100000+76500+72503+60036+57032.5+51333+50700+50000+49500+48000+48000+46523+45000+43646+40000+37978.94+37286+33800+31488+30000+30000+30000+29316+28193.35+25083+20282+20000+19709.89+19000+17432.27+14121+12744+12621+12486+10696+10325.7+8040+7983.91+6940.35+6500+6200+5420+5400+5040+4800+4172+3490+3483.84+3480+3418.8+3381+3198+3065+3011+3000+2846+2670+2400+2275+2250+1935+1920+1666+1333+1320+1300+1275.6+1112+1103+1064+1000+920+900+900+884+878.4+864+816+814+800+745+664.68+565+558+525+450+402.6+375+370+367+320+315.25+312+308+292+202+187.5+182+176+176+140+84+54+22+15.5

144 1052747+1000000+1000000+1000000+700000+502148.92+450000+450000+450000+400000+320000+315000+310000+300000+300000+300000+294556+290000+250000+200000+200000+200000+200000+178000+153000+150000+150000+140718+135000+126420+110573+100000+97828.6+72503+70729+67608+60036+60000+59600+57032.5+50700+50000+50000+48000+45000+45000+40000+37622+37286+36483+33800+33000+32093.8+31488+30000+30000+30000+29837+29572.4+29455+29316+28000+24000+24000+21391+20156+19909+19709.89+16484+16148+16000+12746+12625+10696+9677.2+9488+9112.5+8898.7+8040+7983.91+7943+7680+6829.76+6725.59+6571.26+6200+5889.6+5849+5566+4442+3952+3710+3490+3381+3369.77+3000+2846+2670+2612.8+2400+2343.7+2286+2275+2250+2216.5+2160+2000+1684+1680+1472+1320+1312+1275.6+1130+1112+1103+1000+1000+900+892+884+878.4+814+800+732+720+500+450+392+383.4+367+330+308+292+182+176+170+140+88.2+75+54+50+32+22
49 5500000+2708400+1000000+1000000+1000000+500000+400000+334398+304465+300000+103920+53500+48000+38970+20000+19000+16000+15000+13674+12900+12621+11455.3+9457+9080+6940.35+6500+5000+4172+4000+3698.42+3348+2200+2000+2000+1944.6+1919+1602+920+900+817.05+800+664.68+565+525+402.6+300+260+210+69

香川群子 · 发表于 2018-8-30 15:25

下面这一组，可能是最接近的答案了：

目标匹配金额组合总额差额个数匹配信息
5118119.21 5118119.21 0.00 89 51107+29455+29316+24000+1684+1000+732+88.2+70+40+15.5+5+-6+79950+45000+33800+4442+2250+69+32+12+600000+300000+250000+197851.08+154322+153000+100000+100000+76500+48000+24000+19000+10325.7+7983.91+6500+5849+3011+2216.5+1944.6+1130+744+315.25+1000000+250000+113010+50000+18760+16484+2051+1597+878.4+745+187.5+200000+110573+100000+48000+16000+10563+9677.2+9457+6725.59+5400+4800+3348+1130+1064+330+300+300+22+300000+200000+40000+40000+40000+33000+31200+19709.89+19009.94+16315.6+10000+6940.35+5523+4360+3381+1112+410

目标匹配金额组合总额差额个数匹配信息
6274324.54 6274324.54 0.00 86 450000+315000+155880+150000+128240+20762+12625+3710+2612.8+2000+1333+1301+1103+1015+477.65+367+292+52+28881+24000+18150+12746+7766.25+2000+1200+800+165+1000000+200000+99000+60000+32093.8+25083+20625+8500+4000+3490+3000+2400+2000+450+202+192+310000+220000+100000+100000+53928+33440+17432.27+14908+3369.77+1015+892+315+50+450000+45000+38970+10696+8000+4864+4160+3698.42+1085.76+884+392+370+90+1000000+502148.92+350000+57032.5+45000+31488+29572.4+20282+3300+3198+1920+1300+1080+375+312+182+59

目标匹配金额组合总额差额个数匹配信息
18760134.22 18760134.21 0.01 123 800000+400000+200000+150000+140718+105277.07+100000+72503+71450+38950+34960+26946+24966+16148+15100+9080+7999.38+6829.76+5566+3514.4+3000+2557+2247+1596+1410+1000+817.05+308+300+126+75+5500000+200000+110432+12621+2842.61+2100+664.68+176+140+1400000+1000000+670000+500000+421387.5+320000+200323.6+148413+124286+30000+27624+13351.62+11008.72+9870.49+8898.7+8040+6200+5889.6+4368+3439+3065+2343.7+2200+1944+1935+816+565+300+180+116+84+500000+165000+112045+30000+12900+6571.26+3483.84+3418.8+2650.98+1666+1385.8+170+300000+178000+50000+26295+9900+8944+7680+5040+3952+1911+864+800+176+1500000+1000000+450000+304465+294556+141140+135000+109758+105000+44790+41242+40000+30920+29837+28193.35+27043+16000+12095+11455.3+1472+1275.6+1000+920+900+520+383.4+246

目标匹配金额组合总额差额个数匹配信息
4381536.21 4381536.20 0.01 40 97828.6+38449+12486+1919+7943+3480+3480+500+210+700000+105034+56000+30000+15000+12308+8322+2846+2275+402.6+400+200000+37286+3997+1680+1312+1052747+45000+19909+15000+3560+2670+54+1100000+688600+53500+21867+20000+14121+900+450

目标匹配金额组合总额差额个数匹配信息
13482598.00 13482598.00 0.00 24 67608+48000+850+70729+2160+2708400+1000000+200000+125982+20156+20000+9488+8500+910+320+334398+11575+110200+83498+15476+8297105+300000+46523+720

同时满足第1，2，5组的精确匹配，第3,4组也都只差1分钱。

哈哈。

香川群子 · 发表于 2018-8-30 15:36

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

增加随机计算次数到5万次，终于得到了能同时满足全部5组精确匹配的解：

组合总额 5118119.21 128240+105277.07+103920+53488+38449+29455+16148+12625+2557+2000+1301+1015+292+88.2+40+15.5+5+-6+30000+18150+4442+2160+800+500+176+670000+500000+500000+100000+38781.8+20156+20000+13090+12308+9870.49+8500+8040+5889.6+3065+3000+2846+1935+910+402.6+300+202+310000+165000+112045+53928+50000+43646+37286+33440+13200+12900+11575+5496.58+2650.98+1666+1015+315+450000+290000+48000+26295+6725.59+5640.22+5400+3698.42+2326.7+1085.76+884+800+370+300+90+54+22+300000+141140+135000+109758+57032.5+40000+40000+31488+31200+29572.4+16896.8+14002+1920+1112+920+660+608+520

组合总额 6274324.54 450000+300000+200000+150000+150000+100000+97828.6+67608+51107+41344.8+24966+9080+6829.76+817.05+477.65+27991+24000+7943+4172+2842.61+664.68+210+140+32+12+250000+200000+154322+125982+60000+48000+32093.8+20625+15000+13674+11008.72+8500+8322+7983.91+6200+5036+2275+1130+450+192+1000000+100000+3997+3369.77+2051+1597+50+1052747+200000+45000+15476+10696+4800+4160+3952+3560+1911+300+688600+105000+59600+53500+46523+45000+28193.35+21867+20282+16000+14653.84+14121+12095+3198+1275.6+720+410+383.4+375

组合总额 18760134.22 500000+315000+140718+71450+48000+38950+34960+24000+12486+9112.5+7999.38+3710+2247+1684+1596+1410+1103+732+300+126+75+70+52+5500000+70729+28881+12746+5420+2000+1200+165+600000+320000+200000+153000+99000+76500+40000+37622+37336.1+30000+25083+13351.62+10325.7+9488+4368+3439+3011+2400+2343.7+1590+565+400+315.25+116+334398+220000+113010+30000+17432.27+16484+1385.8+878.4+745+187.5+8000000+300000+178000+100000+83498+45000+30000+12744+10563+9900+9457+1064+392+330+595570+44790+33000+30000+17250+10000+4760+1320+312+246+182+59

组合总额 4381536.21 155880+36483+30000+29316+3514.4+3000+2612.8+1333+1000+575+525+28000+3480+2250+69+1000000+700000+200323.6+100000+60000+56000+50000+49500+37978.94+30000+8898.7+4000+3000+2216.5+2200+744+180+84+200000+100000+51200+18760+3418.8+892+19909+16000+9311+7680+5040+4864+3348+176+502148.92+450000+200000+41242+40000+30920+29837+20000+6940.35+5523+3381+2286+1472+1300+1273.2+1000+450

组合总额 13482598.00 800000+400000+72503+50700+36144.5+26946+5566+1919+1000+308+110432+45000+33800+2100+1000000+124286+60036+19000+6500+3490+2000+1944.6+1944+1602+816+8000+1312+170+600000+450000+110573+110200+45000+15000+1130+8297105+1000000+16315.6+11455.3+5000+3300

以上5组的要求同时满足了。

三坛老窖 · 发表于 2018-8-30 16:40

香川群子发表于 2018-8-30 15:36
增加随机计算次数到5万次，终于得到了能同时满足全部5组精确匹配的解：

组合总额 5118119.21 128240+ ...

这一溜贴刷的，也就是你香侠了，呵呵……

我的求子集和程序，目前没有考虑数据元素包含负数的情况，使用的就是被你称为全组合的算法（其实不是的，应该是动态规划的变种），应能弥补你的求子集和问题程序的部分不足。

楼上这组数据，对其提供的每一个和值，若以标号组合计，估计存在10w以上的精确解，也就是说解很密实。所以用你的这个程序能轻易的找到精确解。

下面这组数据是我以前设计用来测试的，有且仅有1组解，如用你的递归或随机程序，若不作针对性的更改，估计没有几天时间，则难以找到它，你可试试。

目标和值：1501234.29
数据元素（109个）：
909910.33 906496.18 815243.02 706248.00 702141.36 623403.04 391006.01 320011.00 306363.00 233679.00 208301.00 200270.10 160065.00 104909.00 91134.00 87089.00 85339.00 80006.00 75097.00 72384.00 70478.00 70386.00 65933.00 48007.00 46095.00 40076.00 39677.00 38772.00 31061.00 20723.00 20055.00 16189.00 12067.00 11487.00 10907.00 10327.00 10091.00 9747.00 9683.00 9619.00 9565.00 9555.00 9491.00 9427.00 9363.00 9299.00 9235.00 9171.00 9167.00 9107.00 9043.00 8979.00 8915.00 8851.00 8787.00 8723.00 8659.00 8652.00 8595.00 8587.00 8531.00 8467.00 8403.00 8339.00 8275.00 8211.00 8147.00 8083.00 8019.00 8007.00 7955.00 7891.00 7827.00 7763.00 7699.00 7672.00 7635.00 7571.00 7507.00 7443.00 7427.00 7379.00 7315.00 6847.00 6438.00 6267.00 5925.00 5687.00 5412.00 5107.00 4899.00 4527.00 4386.00 3947.00 3873.00 3367.00 3360.00 2847.00 2787.00 2334.00 2207.00 1821.00 1627.00 1308.00 1047.00 795.00 467.00 282.00 97.00

一把小刀闯天下 · 发表于 2018-8-30 21:00

三坛老窖发表于 2018-8-30 16:40
这一溜贴刷的，也就是你香侠了，呵呵……

我的求子集和程序，目前没有考虑数据元素包含负数的情况，使 ...

三坛老师，我用笨办法试了一下确实只得到一组解

先目测从7个含小数的数中凑小数位0.29，只有一种情况：906496.18+391006.01+200270.1=1497772.29
此时所求的合数就变为：1501234.29-1497772.29=3462

那么其余符合条件的非小数只有14个数（<=3462）：3367 3360 2847 2787 2334 2207 1821 1627 1308 1047 795 467 282 97

从这14个数凑和为3462也只有一种组合，把前面3个已得到的数放在一起就可以得到最终组合：
200270.1+391006.01+906496.18+97+282+467+795+1821=1501234.29

三坛老窖 · 发表于 2018-8-30 21:13

一把小刀闯天下发表于 2018-8-30 21:00
三坛老师，我用笨办法试了一下确实只得到一组解

先目测从7个含小数的数中凑小数位0.29，只有一种情况 ...

这是我设计这组数据的思路，目的是少了906496.18、391006.01、200270.1这三个数中的任意一个，就得不到尾数为.29的和值。
如果用代码实现你目测的动作，似乎无从着手。

香川群子 · 发表于 2018-8-31 09:59

本帖最后由香川群子于 2018-8-31 10:00 编辑

三坛老窖发表于 2018-8-30 16:40
这一溜贴刷的，也就是你香侠了，呵呵……

我的求子集和程序，目前没有考虑数据元素包含负数的情况，使 ...

你小看我的凑数程序计算能力了。

我的递归剪枝算法，是独步天下的。

在递归100万次以内找到1组解，耗时仅1.4秒。
（但这是进行了正确的参数设置，如按照遍历全部组合，确实耗时巨大）

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

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

评分