How to find out which numbers in the text add up to a specified value - China DOS Union Forum

Just give one randomly? Then it can only be that replacing the 39th one with 4764... Then there is a unique solution...

This depends on the situation. Otherwise, the amount of calculation is too large. You see the number of accumulation times I mentioned! Tens of powers of 2...

The method I think is the most economical is:
1. Sorting
2. Judging the number of numbers at least and at most.
3. Enumerating the numbers in these 2...
( I'll find this enumeration process later, too lazy to think again, but the more numbers, the more the operation...)

Here comes permutations and combinations again!

There is no simple algorithm.

n = number of numbers in the array
r = from 1 to the sum of numbers in the array
Enumerate in nCr to see if there is a match.....

This kind of program is not suitable to run on a 32-bit system after being written...

--------------------------------------
If only to solve this problem, the recursive code of brother qzwqzw can be slightly modified.
But the calculation speed still depends on luck........


@ECHO %DBG% OFF
SETLOCAL ENABLEDELAYEDEXPANSION

SET /A THE=171780
FOR /F %%n IN (TEST.TXT) DO (
                          SET /A i+=1
                          SET gn!i!=%%n
                          )
FOR /L %%j IN (1,1,%i%) DO CALL :REC %%j
GOTO :EOF

:REC
SETLOCAL

CALL SET tmp=%%gn%1%%
SET /A sum+=%tmp%
IF %sum% GTR %THE% GOTO :EOF
SET /A lvl+=1
IF %lvl% GTR 1 (
                SET exp=%exp%+%tmp%
                SET /A idx+=1
                CLS & ECHO 第 !idx! 次计算
                IF !sum! EQU %THE% (
                                    ECHO !exp!=%sum%
                                    ECHO 继续计算请按任意键&PAUSE>NUL
                                    )
                ) ELSE (
                        SET exp=%tmp%
                        )

SET /A nxt=%1+1
FOR /L %%j IN (%nxt%,1,%i%) DO CALL :REC %%j

ENDLOCAL & SET idx=%idx%
GOTO :EOF

Good luck!
Got the first result when performing the 103rd calculation:


4816+4776+4498+4616+4948+4684+4710+5266+4760+5168+4770+5134+5076+4784+5174+4732+4782+4746+4730+5224+5164+4742+4724+4730+4762+4162+4188+4830+4942+4072+4270+4520+4808+5130+4238+5104=171780

Still that sentence, this problem is not suitable to be solved in a 32-bit system environment.
The following attachment is 321 results obtained after 220,000 calculations!!!!!!

[ Last edited by qjbm on 2007-3-3 at 02:29 PM ]

TO 26F:
If considering repeated numbers,
The largest number combination is only 35, not 38!
The smallest number combination requires 38.
So, the actual number of digits can be 35, 36, 37, 38, etc.
If following the conventional method, according to the permutation and combination rules, the number will be extremely large! I have announced my withdrawal and look forward to experts.

Originally posted by youxi01 at 2007-3-3 12:21:
TO 26F:
If considering repeated numbers,
The largest number combination only has 35, not 38!
The smallest number combination needs 38
So, the real number of digits has cases such as 35, 36, 37, 38, etc.
Such as...

Oh, got the meaning......

[ Last edited by slore on 2007-3-3 at 12:47 PM ]

No way, the efficiency is so low. Then when I get old, it might not be fully calculated yet

Under ideal conditions, filter from these results.
72!/(35!(72-35)!) + 72!/(36!(72-36)!) + 72!/(37!(72-37)!) + 72!/(38!(72-38)!)

72!/35!(72-35)! + 72!/36!(72-36)! + 72!/37!(72-37)! + 72!/38!(72-38)!

n = number of elements in the array
r = from 35 to 38
Enumerate in nCr to see if there are eligible ones.....

The same. Massive calculation mode!!

Batch processing should be something that can't be completed...

Gave up...
The enumeration code has been written... It's too slow for the operation.
No response... Closed. Too many numbers..

Why doesn't the person upstairs publish the code so that we can learn from it?

Not written with p...
The P operation is even slower...

It's recursion and so on... Search online for combination recursion. There are many algorithms, for Delphi, C, VB...

Then can the brother provide the C language code?

http://topic.csdn.net/t/20031003/10/2322382.html

http://www.ycgczj.com.cn/53677.html

The idea seems basically to be recursive backtracking

I don't know why, the 36-digit combinations I wrote out are much more numerous than the groups of 32F?! The code is more efficient than 32F, but it's still not enough. I'm testing it and will post it later.

The code is as follows, welcome to test and give corrections.


@echo off
setlocal enabledelayedexpansion
set num=0
for /f %%n in (test.txt) do (
    set /a i+=1
    set gn!i!=%%n
)
for /l %%i in (1,1,36) do call :rec %%i
pause
goto :eof

:rec
setlocal
set tmp=!gn%1!
set/a flag+=1
if %flag% EQU 1  (set str=%tmp%) else set str=%str%+%tmp%
set/a sum=%sum%+%tmp%
set /a nxt1=%1+1,nxt2=%1+36
if %nxt2% gtr 72 set/a nxt2=72
set /a lvl+=1
if %lvl% lss 36 (
   for /l %%j in (%nxt1%,1,%nxt2%) do call :rec %%j
) else (
      set/a idx+=1
      title Detecting group number %idx%  %num% groups detected
      if %sum% EQU 171780  echo %str%=171780 is in group number %idx% & set/a num+=1
 )
endlocal & set idx=%idx% & set num=%num%

Description: This section of code is for the situation when there are 36 number combinations. Other situations are not considered. Please change it yourself if needed.

[ Last edited by youxi01 on 2007-3-4 at 07:50 AM ]

Floor31　slore	Posted 2007-03-03 22:05
铂金会员　Posts 2,478　Credits 5,212
Just give one randomly? Then it can only be that replacing the 39th one with 4764... Then there is a unique solution... This depends on the situation. Otherwise, the amount of calculation is too large. You see the number of accumulation times I mentioned! Tens of powers of 2... The method I think is the most economical is: 1. Sorting 2. Judging the number of numbers at least and at most. 3. Enumerating the numbers in these 2... ( I'll find this enumeration process later, too lazy to think again, but the more numbers, the more the operation...)

Floor32　qjbm	Posted 2007-03-04 00:21
初级用户　Posts 44　Credits 125
Here comes permutations and combinations again! There is no simple algorithm. n = number of numbers in the array r = from 1 to the sum of numbers in the array Enumerate in nCr to see if there is a match..... This kind of program is not suitable to run on a 32-bit system after being written... -------------------------------------- If only to solve this problem, the recursive code of brother qzwqzw can be slightly modified. But the calculation speed still depends on luck........ @ECHO %DBG% OFF SETLOCAL ENABLEDELAYEDEXPANSION SET /A THE=171780 FOR /F %%n IN (TEST.TXT) DO ( SET /A i+=1 SET gn!i!=%%n ) FOR /L %%j IN (1,1,%i%) DO CALL :REC %%j GOTO :EOF :REC SETLOCAL CALL SET tmp=%%gn%1%% SET /A sum+=%tmp% IF %sum% GTR %THE% GOTO :EOF SET /A lvl+=1 IF %lvl% GTR 1 ( SET exp=%exp%+%tmp% SET /A idx+=1 CLS & ECHO 第 !idx! 次计算 IF !sum! EQU %THE% ( ECHO !exp!=%sum% ECHO 继续计算请按任意键&PAUSE>NUL ) ) ELSE ( SET exp=%tmp% ) SET /A nxt=%1+1 FOR /L %%j IN (%nxt%,1,%i%) DO CALL :REC %%j ENDLOCAL & SET idx=%idx% GOTO :EOF Good luck! Got the first result when performing the 103rd calculation: 4816+4776+4498+4616+4948+4684+4710+5266+4760+5168+4770+5134+5076+4784+5174+4732+4782+4746+4730+5224+5164+4742+4724+4730+4762+4162+4188+4830+4942+4072+4270+4520+4808+5130+4238+5104=171780 Still that sentence, this problem is not suitable to be solved in a 32-bit system environment. The following attachment is 321 results obtained after 220,000 calculations!!!!!! [ Last edited by qjbm on 2007-3-3 at 02:29 PM ] Attachments 结果.txt (60.98 KiB)

Floor33　youxi01	Posted 2007-03-04 01:21
高级用户　Posts 247　Credits 846　From 湖南==》广东
TO 26F: If considering repeated numbers, The largest number combination is only 35, not 38! The smallest number combination requires 38. So, the actual number of digits can be 35, 36, 37, 38, etc. If following the conventional method, according to the permutation and combination rules, the number will be extremely large! I have announced my withdrawal and look forward to experts.

Floor34　slore	Posted 2007-03-04 01:31
铂金会员　Posts 2,478　Credits 5,212
Originally posted by youxi01 at 2007-3-3 12:21: TO 26F: If considering repeated numbers, The largest number combination only has 35, not 38! The smallest number combination needs 38 So, the real number of digits has cases such as 35, 36, 37, 38, etc. Such as... Oh, got the meaning...... [ Last edited by slore on 2007-3-3 at 12:47 PM ]

Floor35　youxi01	Posted 2007-03-04 03:12
高级用户　Posts 247　Credits 846　From 湖南==》广东
No way, the efficiency is so low. Then when I get old, it might not be fully calculated yet

Floor36　20080610	Posted 2007-03-04 03:41
初级用户　Posts 34　Credits 83
Under ideal conditions, filter from these results. 72!/(35!(72-35)!) + 72!/(36!(72-36)!) + 72!/(37!(72-37)!) + 72!/(38!(72-38)!)

Floor37　qjbm	Posted 2007-03-04 03:48
初级用户　Posts 44　Credits 125
72!/35!(72-35)! + 72!/36!(72-36)! + 72!/37!(72-37)! + 72!/38!(72-38)! n = number of elements in the array r = from 35 to 38 Enumerate in nCr to see if there are eligible ones..... The same. Massive calculation mode!!

Floor38　20080610	Posted 2007-03-04 03:50
初级用户　Posts 34　Credits 83
Batch processing should be something that can't be completed...

Floor39　slore	Posted 2007-03-04 05:26
铂金会员　Posts 2,478　Credits 5,212
Gave up... The enumeration code has been written... It's too slow for the operation. No response... Closed. Too many numbers..

Floor40　Primalchaos	Posted 2007-03-04 05:28
初级用户　Posts 19　Credits 41
Why doesn't the person upstairs publish the code so that we can learn from it?

Floor41　slore	Posted 2007-03-04 05:41
铂金会员　Posts 2,478　Credits 5,212
Not written with p... The P operation is even slower... It's recursion and so on... Search online for combination recursion. There are many algorithms, for Delphi, C, VB...

Floor42　Primalchaos	Posted 2007-03-04 06:19
初级用户　Posts 19　Credits 41
Then can the brother provide the C language code?

Floor43　slore	Posted 2007-03-04 06:35
铂金会员　Posts 2,478　Credits 5,212
http://topic.csdn.net/t/20031003/10/2322382.html http://www.ycgczj.com.cn/53677.html The idea seems basically to be recursive backtracking

Floor44　youxi01	Posted 2007-03-04 07:34
高级用户　Posts 247　Credits 846　From 湖南==》广东
I don't know why, the 36-digit combinations I wrote out are much more numerous than the groups of 32F?! The code is more efficient than 32F, but it's still not enough. I'm testing it and will post it later.

Floor45　youxi01	Posted 2007-03-04 07:48
高级用户　Posts 247　Credits 846　From 湖南==》广东
The code is as follows, welcome to test and give corrections. @echo off setlocal enabledelayedexpansion set num=0 for /f %%n in (test.txt) do ( set /a i+=1 set gn!i!=%%n ) for /l %%i in (1,1,36) do call :rec %%i pause goto :eof :rec setlocal set tmp=!gn%1! set/a flag+=1 if %flag% EQU 1 (set str=%tmp%) else set str=%str%+%tmp% set/a sum=%sum%+%tmp% set /a nxt1=%1+1,nxt2=%1+36 if %nxt2% gtr 72 set/a nxt2=72 set /a lvl+=1 if %lvl% lss 36 ( for /l %%j in (%nxt1%,1,%nxt2%) do call :rec %%j ) else ( set/a idx+=1 title Detecting group number %idx% %num% groups detected if %sum% EQU 171780 echo %str%=171780 is in group number %idx% & set/a num+=1 ) endlocal & set idx=%idx% & set num=%num% Description: This section of code is for the situation when there are 36 number combinations. Other situations are not considered. Please change it yourself if needed. [ Last edited by youxi01 on 2007-3-4 at 07:50 AM ]