Excel sum cells to an established number

[ivill]

Hi all, For example, The established number is 500000(maybe i shall create an input box), how to use COMobjExcel way to pick the right cells in column A which can get the sum result 500000? as the attachment image shown, there are two or more answers, the yellow and blue background colored cells, simply pick a set of numbers randomly.
Appreciate!

[IMEime]

Actually, this is all about VBA though final appearance is AHK

by the way

Where is your code ?
Do it yourself
When you have some difficulties, then post help, not all of them.

Good Luck

[jeeswg]

This is combinatorics stuff, it often helps to produce numbers in a particular base e.g. binary. Here's some code to solve the mathematical part of the problem.

Code: Select all

q:: ;add a subset of numbers to reach a total
oArray := [10, 20, 30, 40, 50, 60]
vTarget := 110
vChoose := 3
vOutput := "target: " vTarget "`r`n"
Loop, % 2**6
{
	vBin := JEE_DecToBin(A_Index-1, 6)
	StrReplace(vBin, "1",, vCount)
	if !(vCount = vChoose)
		continue
	vSum := 0
	Loop, Parse, vBin
		if A_LoopField
			vSum += oArray[A_Index]
	if (vSum = vTarget)
	{
		vList := ""
		Loop, Parse, vBin
			if A_LoopField
				vList .= (vList=""?"":",") oArray[A_Index]
		vOutput .= vBin "`t" vList "`r`n"
	}
}
;Clipboard := vOutput
MsgBox, % vOutput
return

;==================================================

;where vLen is the minimum length of the number to return (i.e. pad it with zeros if necessary)
;JEE_Dec2Bin
JEE_DecToBin(vNum, vLen:=1)
{
	local
	;convert '0x' form to dec
	if !RegExMatch(vNum, "^\d+$")
		vNum += 0
	if !RegExMatch(vNum, "^\d+$")
		return
	vBin := ""
	while vNum
		vBin := (vNum & 1) vBin, vNum >>= 1
	return Format("{:0" vLen "}", vBin)

	;if (StrLen(vBin) < vLen)
	;	Loop, % vLen - StrLen(vBin)
	;		vBin := "0" vBin
	;return vBin
}

[FanaticGuru]

This is combinatorics stuff, it often helps to produce numbers in a particular base e.g. binary. Here's some code to solve the mathematical part of the problem.

Code: Select all

q:: ;add a subset of numbers to reach a total
oArray := [10, 20, 30, 40, 50, 60]
vTarget := 110
vChoose := 3
vOutput := "target: " vTarget "`r`n"
Loop, % 2**6
{
	vBin := JEE_DecToBin(A_Index-1, 6)
	StrReplace(vBin, "1",, vCount)
	if !(vCount = vChoose)
		continue
	vSum := 0
	Loop, Parse, vBin
		if A_LoopField
			vSum += oArray[A_Index]
	if (vSum = vTarget)
	{
		vList := ""
		Loop, Parse, vBin
			if A_LoopField
				vList .= (vList=""?"":",") oArray[A_Index]
		vOutput .= vBin "`t" vList "`r`n"
	}
}
;Clipboard := vOutput
MsgBox, % vOutput
return

;==================================================

;where vLen is the minimum length of the number to return (i.e. pad it with zeros if necessary)
;JEE_Dec2Bin
JEE_DecToBin(vNum, vLen:=1)
{
	local
	;convert '0x' form to dec
	if !RegExMatch(vNum, "^\d+$")
		vNum += 0
	if !RegExMatch(vNum, "^\d+$")
		return
	vBin := ""
	while vNum
		vBin := (vNum & 1) vBin, vNum >>= 1
	return Format("{:0" vLen "}", vBin)

	;if (StrLen(vBin) < vLen)
	;	Loop, % vLen - StrLen(vBin)
	;		vBin := "0" vBin
	;return vBin
}

Changed the code to get all subset sizes from any size set.

Code: Select all

oArray := [10, 20, 30, 40, 50, 60, 110]
vTarget := 110
;~ vChoose := 4
N := oArray.Length()
vOutput := "target: " vTarget "`r`n"
Loop % N
{
	vChoose := A_Index
	Loop, % 2**N
	{
		vBin := JEE_DecToBin(A_Index-1, N)
		StrReplace(vBin, "1",, vCount)
		if !(vCount = vChoose)
			continue
		vSum := 0
		Loop, Parse, vBin
			if A_LoopField
				vSum += oArray[A_Index]
		if (vSum = vTarget)
		{
			vList := ""
			Loop, Parse, vBin
				if A_LoopField
					vList .= (vList=""?"":",") oArray[A_Index]
			vOutput .= vBin "`t" vList "`r`n"
		}
	}
}
;Clipboard := vOutput
MsgBox, % vOutput
return

;==================================================

;where vLen is the minimum length of the number to return (i.e. pad it with zeros if necessary)
;JEE_Dec2Bin
JEE_DecToBin(vNum, vLen:=1)
{
	local
	;convert '0x' form to dec
	if !RegExMatch(vNum, "^\d+$")
		vNum += 0
	if !RegExMatch(vNum, "^\d+$")
		return
	vBin := ""
	while vNum
		vBin := (vNum & 1) vBin, vNum >>= 1
	return Format("{:0" vLen "}", vBin)

	;if (StrLen(vBin) < vLen)
	;	Loop, % vLen - StrLen(vBin)
	;		vBin := "0" vBin
	;return vBin
}

I have normally seen this done with just a bool array of true and false instead of a string of binary numbers. It is the same concept but an array would almost certainly be faster.

It is important to also realize this is a naïve algorithm using brute force to solve for every combination which has a solve time of O((2**N)N) which means it is an exponential time algorithm. If the number of items gets very large at all the number of calculations gets too much to handle.

Just a set of 20 numbers puts the number of loops at over 20 million. 30 numbers is 32 billion loops. So this solution is only useful for relatively small sets. Just in my simple test a set with 15 numbers takes about 12 seconds to solve with the above code.

There are other more complex algorithms that can handle large sets of numbers but the sum looked for must be relatively small. With the OP example the naïve algorithm requires 49,152 loops. The standard dynamic programming solution would require 6,000,000 loops because it is not well suited for looking for a large sum like 500,000. There are a lot of different variations of dynamic programming solutions depending on the data sets expected.

This is an NP-Complete problem which means there is no efficient solution to this problem that works regardless of the data sets.

Great example, jeeswg. I am just not sure if the OP is aware of the complexity of the problem. Not just for AHK or computer programming, this is a classic math problem that has been around and studied for decades.

FG

[FanaticGuru]

Here is a different naïve algorithm that uses the OP data.

Code: Select all

Set := [100000,250000,80000,150000,20000,60000,75000,15000,90000,85000,360000,10000]
Target := 500000

Results := Sum_Sets(Set, Target)
for Index, SubSet in Results
{
  Display .= "`n" Index ")  "
  for Index2, Value in SubSet
    Display .= Value "  "
}
MsgBox % Display

Sum_Sets(ByRef Arr, Target)
{
  Results := {}, Sets := {}
  for Index, Val in Arr
  {
    L := Sets.Length(), J := -1
    while (J++ < L)
    {
      if !J
        SubSet := {1:Val}
      else
      {
        SubSet := Sets[J].Clone()
        SubSet.Push(Val)
      }
      Sum := 0
      for x, y in SubSet
        Sum += y
      if (Sum = Target)
        Results.Push(SubSet.Clone())
      Sets.Push(SubSet.Clone())
    }
  }
  return Results
}

It is about 30 times faster than jeeswg example with the OP data. It is still way too slow though once the size of the set gets into the high teens.

Also with the OP data there is 29 combinations which is more than most people might think at first glance.

FG