Combination of sums equal to target value
Solved
ask Answer
-
Jeremie -
Jeremie -
Hello,
Using Microsoft Excel 2007 I want to do the following:
I have a database of values (numbers) and I have a target value. I want to find all the possible combinations of sums of the numbers (from the database) that equal the target value.
Is this possible?
Configuration: Windows 7 / Safari 535.11
Using Microsoft Excel 2007 I want to do the following:
I have a database of values (numbers) and I have a target value. I want to find all the possible combinations of sums of the numbers (from the database) that equal the target value.
Is this possible?
Configuration: Windows 7 / Safari 535.11
13 answers
Hello,
Check if this program works for you:
https://www.cjoint.com/?BEushEb54QO
The explanations of the parameters are commented in the cells.
eric
Check if this program works for you:
https://www.cjoint.com/?BEushEb54QO
The explanations of the parameters are commented in the cells.
eric
A big thank you, Eric. This is very useful and beautiful.
I just noticed that the program doesn't work correctly if:
1- I insert a negative number in the "value" column and/or the target value cell.
2- I insert columns before the "value" column (a "Type incompatibility" message appears).
Please, is there a solution for these?
Thank you.
I just noticed that the program doesn't work correctly if:
1- I insert a negative number in the "value" column and/or the target value cell.
2- I insert columns before the "value" column (a "Type incompatibility" message appears).
Please, is there a solution for these?
Thank you.
The file is originally designed to paste values into it. If you insert or delete rows or columns, the macro gets confused. It needs to be modified accordingly.
And it's true that I had looked into finding sums of positive numbers (finding the lines of a grouped invoice when you only have the total)
Do you want to explain your issue to see if there are other specific cases or possibilities for a workaround?
Eric
PS: After testing, it seems to respond well with negative numbers.
And it's true that I had looked into finding sums of positive numbers (finding the lines of a grouped invoice when you only have the total)
Do you want to explain your issue to see if there are other specific cases or possibilities for a workaround?
Eric
PS: After testing, it seems to respond well with negative numbers.
In fact, the need for such an application arose from the fact that I work in the financial sector.
I have a financial balance database (with at least 3 columns: Account No, Description, and Amount). The company provides me with financial statements in which each item has an amount (which is actually a summation of a set of accounts from the balance). Since the number of lines in the balance is generally very large, I spend days trying to find the balance amounts that match the items in the financial statements. The amounts in the balance can be either positive or negative.
What do you think?
I have a financial balance database (with at least 3 columns: Account No, Description, and Amount). The company provides me with financial statements in which each item has an amount (which is actually a summation of a set of accounts from the balance). Since the number of lines in the balance is generally very large, I spend days trying to find the balance amounts that match the items in the financial statements. The amounts in the balance can be either positive or negative.
What do you think?
So you need an additional column, right?
And I just saw that you were talking about the target cell in negative.
It's normal that it doesn't work.
To eliminate thousands (even hundreds of thousands) of tests, I exit a loop as soon as the sum is exceeded.
Removing this optimization would result in unbearable response times.
You need to reverse your numbers in this case:
- enter -1 in a cell and copy it.
- select the range and 'special paste multiplication'
eric
And I just saw that you were talking about the target cell in negative.
It's normal that it doesn't work.
To eliminate thousands (even hundreds of thousands) of tests, I exit a loop as soon as the sum is exceeded.
Removing this optimization would result in unbearable response times.
You need to reverse your numbers in this case:
- enter -1 in a cell and copy it.
- select the range and 'special paste multiplication'
eric
Hello,
Here are 5 columns.
Added:
- handling a negative target sum (without manual manipulation).
- a double click on a solution filters the relevant values.
- a double click on an active filter cancels it.
https://www.cjoint.com/?BEvjNdp8qA8
Normally debugged, but if you can test thoroughly and report any issues not too late...
eric
Here are 5 columns.
Added:
- handling a negative target sum (without manual manipulation).
- a double click on a solution filters the relevant values.
- a double click on an active filter cancels it.
https://www.cjoint.com/?BEvjNdp8qA8
Normally debugged, but if you can test thoroughly and report any issues not too late...
eric
Hello,
here it is: https://www.cjoint.com/c/CBmqwkGmHcg
eric
--
You will never respond to an unsolicited DM...
Well, that's done.
here it is: https://www.cjoint.com/c/CBmqwkGmHcg
eric
--
You will never respond to an unsolicited DM...
Well, that's done.
Hello,
Yes, but let's imagine we have a list of fairly high and precise numbers, with several digits after the decimal, that would greatly limit the number of possible combinations..
No, it may decrease the number of solutions.
But the number of combinations (they all need to be explored) is exponential. If you really have a lot of values, expect very long processing times, even extremely long.
In any case, it seemed like an interesting evolution to me, I tried...
If you could give me feedback on how well it works.
And out of curiosity, the number of values and the time taken.
https://www.cjoint.com/c/CBom4p3UbC6
eric
--
You will never respond to an unsolicited message...
Well, that's done.
Yes, but let's imagine we have a list of fairly high and precise numbers, with several digits after the decimal, that would greatly limit the number of possible combinations..
No, it may decrease the number of solutions.
But the number of combinations (they all need to be explored) is exponential. If you really have a lot of values, expect very long processing times, even extremely long.
In any case, it seemed like an interesting evolution to me, I tried...
If you could give me feedback on how well it works.
And out of curiosity, the number of values and the time taken.
https://www.cjoint.com/c/CBom4p3UbC6
eric
--
You will never respond to an unsolicited message...
Well, that's done.
Good evening,
Actually, these are not crashes; it's more about regaining control of the macro during long calculations.
With 65 values, it can take a very long time, several hours... It has to explore all combinations, several millions.
If you set nbTermesmini=7, you exclude all combinations of sums from 2 to 6 terms, and you'll see that the solution is found quite quickly (in 30 seconds, without waiting for hours).
I changed the logic a bit and added a form that provides elements to see the progress of the macro. It also allows for pauses or stopping the analysis.
https://www.cjoint.com/c/DCrxbr4PYST
Eric
In addition to the thank you (yes, it’s done!!!), please remember to mark it as resolved when that's the case (at the top near your title).
Thank you.
Actually, these are not crashes; it's more about regaining control of the macro during long calculations.
With 65 values, it can take a very long time, several hours... It has to explore all combinations, several millions.
If you set nbTermesmini=7, you exclude all combinations of sums from 2 to 6 terms, and you'll see that the solution is found quite quickly (in 30 seconds, without waiting for hours).
I changed the logic a bit and added a form that provides elements to see the progress of the macro. It also allows for pauses or stopping the analysis.
https://www.cjoint.com/c/DCrxbr4PYST
Eric
In addition to the thank you (yes, it’s done!!!), please remember to mark it as resolved when that's the case (at the top near your title).
Thank you.
Hello Eric,
Thank you very much for your work that saves my life! However, my problem is not completely resolved, as I have a list of numbers (about 350) and I want to make combinations to reach my target value of 6. How is it possible to rerun the calculation while ignoring the values taken into account in the first combination?
Example:
I enter the values
1
3
5
2
6
4
1
My target value is 8
The first result I get is indeed the combination of the values 5 and 3
I would then like the program to continue running so that all my values are associated:
2nd result: 6+2
3rd result: 4+1+1
??
I hope you can shed some light on this point, otherwise thank you anyway!
Fanny
Thank you very much for your work that saves my life! However, my problem is not completely resolved, as I have a list of numbers (about 350) and I want to make combinations to reach my target value of 6. How is it possible to rerun the calculation while ignoring the values taken into account in the first combination?
Example:
I enter the values
1
3
5
2
6
4
1
My target value is 8
The first result I get is indeed the combination of the values 5 and 3
I would then like the program to continue running so that all my values are associated:
2nd result: 6+2
3rd result: 4+1+1
??
I hope you can shed some light on this point, otherwise thank you anyway!
Fanny
Hello,
I'm following up on this topic that interests me a lot,
I've taken your initial macro to try to modify it for my problem.
My issue: I have a list of numbers ranging from 1 to 33, and I want to find the best possible combinations to be either equal to 33 or as close to 33 as possible.
Knowing that each number must be used only once.
I hope I was clear in my explanation, and how can we modify it so that the numbers are no longer in euros, but integers?
Thank you in advance.
I'm following up on this topic that interests me a lot,
I've taken your initial macro to try to modify it for my problem.
My issue: I have a list of numbers ranging from 1 to 33, and I want to find the best possible combinations to be either equal to 33 or as close to 33 as possible.
Knowing that each number must be used only once.
I hope I was clear in my explanation, and how can we modify it so that the numbers are no longer in euros, but integers?
Thank you in advance.
Hello,
how can we modify so that the numbers are no longer in euros, but integers.
You just need to change the cell format (right-click on the cells)
However, in the code keep the variables typed as Currency, otherwise you might miss the exact solution.
This program does not look for the closest solution, that is not its purpose...
eric
how can we modify so that the numbers are no longer in euros, but integers.
You just need to change the cell format (right-click on the cells)
However, in the code keep the variables typed as Currency, otherwise you might miss the exact solution.
This program does not look for the closest solution, that is not its purpose...
eric
Thank you very much!
Quick question: Would it be possible to allow the combination of several negative numbers and several positive numbers to reach a given result??
When combining a negative and a positive (e.g., to find -5, the system combines “-6” and “1”), it works.
But if we try several negatives with several positives (e.g., to find -17, the system would combine “-15”, “3”, “-7” and “2” =??), it doesn’t work.
HELP!!!
Quick question: Would it be possible to allow the combination of several negative numbers and several positive numbers to reach a given result??
When combining a negative and a positive (e.g., to find -5, the system combines “-6” and “1”), it works.
But if we try several negatives with several positives (e.g., to find -17, the system would combine “-15”, “3”, “-7” and “2” =??), it doesn’t work.
HELP!!!
Hello,
I don't think you've read post 5.
To eliminate thousands (or even hundreds of thousands) of tests, I exit a loop as soon as the sum is exceeded.
Removing this optimization would result in unbearable response times.
In your case, I suggest adding 20 to all your numbers, including the target total, and performing the reverse operation at the end.
Eric
I don't think you've read post 5.
To eliminate thousands (or even hundreds of thousands) of tests, I exit a loop as soon as the sum is exceeded.
Removing this optimization would result in unbearable response times.
In your case, I suggest adding 20 to all your numbers, including the target total, and performing the reverse operation at the end.
Eric
Yes, but let's imagine we have a list of fairly high and precise numbers, with several digits after the decimal point; that would greatly limit the number of possible combinations... Is the idea still not feasible? 8-)
Thank you for the work Eric, your file helped me a lot. I did a test using a database consisting of 65 amounts, the target value contains 7 amounts, but after 3 consecutive tests of 3 minutes, no solution was found.
Why is there no solution, even though my database is small?
I would like an answer, thank you.
Why is there no solution, even though my database is small?
I would like an answer, thank you.
Hello (usually we start with that...),
Check that nbTermesMaxi in H4 is set to a sufficient value before running the macro.
For safety, set it to 65.
And do not check 'Remove duplicates'. You have to do it knowingly, it removes solutions.
Now, are you 100% sure there is necessarily a solution? Perhaps some invoices are missing.
Out of curiosity, paste your amounts and the total to reach here.
And if you know the combination that reaches the total, provide it as well.
eric
Check that nbTermesMaxi in H4 is set to a sufficient value before running the macro.
For safety, set it to 65.
And do not check 'Remove duplicates'. You have to do it knowingly, it removes solutions.
Now, are you 100% sure there is necessarily a solution? Perhaps some invoices are missing.
Out of curiosity, paste your amounts and the total to reach here.
And if you know the combination that reaches the total, provide it as well.
eric
Hello Eric, regarding your question, yes, I followed the rules and I know the combination; it is just the addition of seven amounts, a very simple formula (a way to do a test).
6,374.31 €
108,541.88 €
75,566.79 €
74,623.24 €
78,587.43 €
2,116.57 €
611,494.40 €
878,328.32 €
1,481,372.72 €
42,256,629.73 €
1,983,360.61 €
1,499,746.41 €
15,976,478.77 €
714,807.00 €
2,194,054.82 €
855,646.34 €
9,571,079.23 €
4,573,078.31 €
1,782,192.29 €
41,286,529.09 €
13,819,675.57 €
68,882.76 €
1,940,295.28 €
1,371,098.28 €
37,156,338.86 €
11,169,637.16 €
1,183,563.46 €
1,746,518.08 €
1,818,206.29 €
1,155,930.90 €
38,677,773.29 €
10,125,099.48 €
38,695,024.69 €
8,777,939.93 €
39,430,615.24 €
7,332,474.17 €
1,093,920.77 €
2,968.32 €
1,795.62 €
1,808,349.55 €
1,842,064.26 €
2,272.28 €
1,027,644.74 €
4,073.10 €
4,327,158.82 €
38,782,450.19 €
881,430.44 €
1,823,045.71 €
37,685,918.39 €
66,104.67 €
2,849,674.72 €
7,375.65 €
803,688.60 €
1,771,655.25 €
1,099.57 €
2,274.23 €
3,574.84 €
704,994.73 €
1,558.49 €
1,723,241.90 €
1,392,345.83 €
285,145.97 €
37,436,926.60 €
21,561.73 €
15,254.21 €
You can take 7 amounts or more from this database and audition it doesn't work for example you can take the first 4 and the last 3 from the database that will make (37,738,848.76 euros) I use your 4th version.
108,541.88 €
75,566.79 €
74,623.24 €
78,587.43 €
2,116.57 €
611,494.40 €
878,328.32 €
1,481,372.72 €
42,256,629.73 €
1,983,360.61 €
1,499,746.41 €
15,976,478.77 €
714,807.00 €
2,194,054.82 €
855,646.34 €
9,571,079.23 €
4,573,078.31 €
1,782,192.29 €
41,286,529.09 €
13,819,675.57 €
68,882.76 €
1,940,295.28 €
1,371,098.28 €
37,156,338.86 €
11,169,637.16 €
1,183,563.46 €
1,746,518.08 €
1,818,206.29 €
1,155,930.90 €
38,677,773.29 €
10,125,099.48 €
38,695,024.69 €
8,777,939.93 €
39,430,615.24 €
7,332,474.17 €
1,093,920.77 €
2,968.32 €
1,795.62 €
1,808,349.55 €
1,842,064.26 €
2,272.28 €
1,027,644.74 €
4,073.10 €
4,327,158.82 €
38,782,450.19 €
881,430.44 €
1,823,045.71 €
37,685,918.39 €
66,104.67 €
2,849,674.72 €
7,375.65 €
803,688.60 €
1,771,655.25 €
1,099.57 €
2,274.23 €
3,574.84 €
704,994.73 €
1,558.49 €
1,723,241.90 €
1,392,345.83 €
285,145.97 €
37,436,926.60 €
21,561.73 €
15,254.21 €
You can take 7 amounts or more from this database and audition it doesn't work for example you can take the first 4 and the last 3 from the database that will make (37,738,848.76 euros) I use your 4th version.
Good evening,
I am reading this post several months later. I retrieved the file and looked at the code (Well done ERIC, really)
I would like to know if it is possible to perform this analysis on a multi-column table?
Explanations (or at least an attempt :-) :
The range A4:A100 contains 96 values and a value in A2 equal to the sum of some of the values in column A
The range B4:B100 contains 96 values and a value in B2 equal to the sum of some of the values in column B
The range C4:C100 contains 96 values and a value in C2 equal to the sum of some of the values in column C
Can we search for the rows that can satisfy both the values of A2, B2, C2?
1°) The values are positive or negative integers
2°) The maximum number of rows to reach the sum is often <=3
If someone is reading this and knows the answer, thank you very much in advance
Best regards
I am reading this post several months later. I retrieved the file and looked at the code (Well done ERIC, really)
I would like to know if it is possible to perform this analysis on a multi-column table?
Explanations (or at least an attempt :-) :
The range A4:A100 contains 96 values and a value in A2 equal to the sum of some of the values in column A
The range B4:B100 contains 96 values and a value in B2 equal to the sum of some of the values in column B
The range C4:C100 contains 96 values and a value in C2 equal to the sum of some of the values in column C
Can we search for the rows that can satisfy both the values of A2, B2, C2?
1°) The values are positive or negative integers
2°) The maximum number of rows to reach the sum is often <=3
If someone is reading this and knows the answer, thank you very much in advance
Best regards
As the topic is old, I'm giving you the latest version in case the error has been fixed.
v4.3.5.3 : https://mon-partage.fr/f/WoZQ8D2P/
2 hours is nothing. With 700 lines, I would have said several days... ;-)
I do have an idea to speed things up, but not for several weeks.
I don't really have the time or the desire to spend hours on it this season.
eric