software

in column A i have a set of numbers. in column B i have a single number
that is the sum of some (not all) of the numbers in column A. i dont
know what numbers from column A will equal the number in column B, nor
do i know how many are added together to do so. but i do know that the
number in column B is a combination of numbers from column A.

its very important that i find a way to do this. any help would be
greatly appreciated.--
spyshot
------------------------------------------------------------------------
spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
View this thread: www.excelforum.com/showthread...hreadid=515054Do you mean that you want a method of generating the number in B, or
that you want to be able to split B up to show which numbers from
column A are added together?

Are the numbers in A in any particular order?

Pete
split up b to show which numbers from a are added together.

no particular order. random

thanks--
spyshot
------------------------------------------------------------------------
spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
View this thread: www.excelforum.com/showthread...hreadid=515054This is actually quite a difficult problem to solve. As a example,
suppose you had the following numbers in column A:

15
12
10
9
7
4
3

and the value in B was 28. You could choose a quot;Largest Fitquot; algorithm,
i.e. choose the largest available number which could be included in the
sum.

In this instance your first choice would be 15, then 12 but then you
find there isn't a 1, so you would discard the 12 and choose 10 and
then you find that 3 fitted the bill, so the answer is 15, 10 and 3.
However, another solution could be 12, 9, 4 and 3, and with a larger
range of numbers there could be many possible solutions.

Suppose, now, the number in B was 26. Again you would choose 15 first,
then 12, and then discard this, choose 10 and then discard this, choose
9 and then discard this, choose 7 then choose 4 to arrive at the
solution. Another solution would be 12, 7, 4 and 3.

The largest fit algorithm would generally find the solution with the
fewest number of additions, but the numbers in A have to be taken in
decreasing order of magnitude for this method to work, and it is
recursive in nature.

Perhaps someone might be encouraged to code the method in VBA for you
....

Hope this helps.

PeteHi,

You could do this using quot;Solverquot;.
Supposing the set of numbers is in A2:A11. Enter 1 in each cell in B2 to
B11. Place the single number in C2. Enter the following formula in some
other cell (say C3)
=SUMPRODUCT(A2:A11,B2:B11)-C2 and click ENTER.

Now you are going to use the Solver (the quot;Solverquot; add-in should be installed
for this) to find the combination of numbers in Column A whose total would be
equal to the single number you have entered in C2. For that,
quot;Toolsquot; --gt; quot;Solverquot; --gt; in quot;Solver Parametersquot; window,

quot;Set Target Cellquot; $C$3
quot;Equal Toquot; quot;Value ofquot; 0
quot;By Changing Cellsquot; $B$2:$B$11
quot;Subject to the Constraintsquot;--gt; click quot;Addquot; --gt; enter $B2$2:$B$11, select
quot;binquot; from the popdown list (This would add a constraint which would read as
quot;$B$2:$B$11=binaryquot;)
Click quot;Solvequot;
The solver would find the solution by changing some of the 1's in Column B
to 0's. The set of Column A numbers for which Column B is 1 (and not 0) is
the solution for your problem. If the solution is satisfactory, click quot;Keep
Solver Solutionquot;. Note that if more than one solution is possible, Solver
would find the first solution.

To add a nice touch, maybe you can use Conditional Formatting to highlight
the numbers in Column A for which Column B is 1.

Regards,
B. R. Ramachandran

quot;spyshotquot; wrote:

gt;
gt; in column A i have a set of numbers. in column B i have a single number
gt; that is the sum of some (not all) of the numbers in column A. i dont
gt; know what numbers from column A will equal the number in column B, nor
gt; do i know how many are added together to do so. but i do know that the
gt; number in column B is a combination of numbers from column A.
gt;
gt; its very important that i find a way to do this. any help would be
gt; greatly appreciated.
gt;
gt;
gt; --
gt; spyshot
gt; ------------------------------------------------------------------------
gt; spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
gt; View this thread: www.excelforum.com/showthread...hreadid=515054
gt;
gt;


thank you everyone for your help! i will give it a try!--
spyshot
------------------------------------------------------------------------
spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
View this thread: www.excelforum.com/showthread...hreadid=515054
thank you everyone for your help! i will give it a try!--
spyshot
------------------------------------------------------------------------
spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
View this thread: www.excelforum.com/showthread...hreadid=515054Here is a VBA routine I wrote which may be what you need. I wrote it in C
originally, and later adapted it to Excel VBA.

To run the code, you will need to add a VBA code module to your workbook and
paste in all the code below. On the worksheet with the data, select all the
numbers in column A (but not the whole column). Run the Knapsack routine by
selecting Macro gt;gt; Macros from the Tools menu. In the list of available
macros that appears, select Knapsack and click Run.

Knapsack will prompt you for a target number. Enter your target number from
column B. Knapsack will use recursion (and iteration) to look for
combinations of numbers which equal the target. It will list the solutions it
finds (if any) on a new worksheet it will add to your workbook.

Knapsack can find multiple solutions but is not guaranteed to find every
possible solution. Also, if your data (column A) includes more than a few
hundred numbers, it may take a long time to complete.

I hope this is helpful. The code:

'Global variables for Knapsack
Public Type RngType
Nbr As Double 'Number in cell
Addr As String 'Address of cell
End Type
Public Cellz() As RngType, Targett As Double, Kount As Currency, RngCnt As
Long, strTarget As String
Public Soln() As RngType, SolnCnt As Long, SolnNbr As Long, SolnRow As Long

Sub Knapsack()
'Calls function KS to find combinations of values within the selection that
total the target number.
'Current LIMITS: only finds target numbers which are positive numbers; can
find multiple solutions,
'but not necessarily every possible solution. Also, if the target is the sum
of the only two numbers in the
'selection which are smaller than the target, it may not find the solution.
Dim c As Range, aa As Long, bb As Long, msg101 As String, Temp() As
RngType, NegFlag As Boolean, BigFlag As Boolean
On Error GoTo KSerr1
'Check if the selected range has gt; 2 cells.
If Selection.Count lt; 3 Then
MsgBox quot;You must select more than 2 cellsquot;, vbExclamation, quot;Are you
kidding?quot;
Exit Sub
End If
'Get the target number from the user.
strTarget$ = InputBox(quot;Enter the target amountquot;)
If Len(strTarget$) = 0 Then Exit Sub
Targett# = CDbl(strTarget$)
'Load range to be checked into Cellz array. Store the address amp; value from
each cell in the selected range.
RngCntamp; = -1
For Each c In Selection
RngCntamp; = RngCntamp; 1
ReDim Preserve Temp(RngCntamp;)
Temp(RngCntamp;).Addr = c.Address
Temp(RngCntamp;).Nbr = c.Value
Next c
'Add one more dummy element to Cellz() to make sure last cell gets tested.
RngCntamp; = RngCntamp; 1
ReDim Preserve Cellz(RngCntamp;)
Cellz(RngCntamp;).Addr = Cellz(RngCntamp; - 1).Addr
Cellz(RngCntamp;).Nbr = 0
'See if there are any negative numbers or numbers larger than Targett# in
Temp().
BigFlag = False
NegFlag = False
For aaamp; = 0 To (RngCntamp; - 1)
If Temp(aaamp;).Nbr lt; 0 Then
NegFlag = True
ElseIf Temp(aaamp;).Nbr gt; Targett# Then
BigFlag = True
End If
Next aaamp;
'If both NegFlag and BigFlag are True (or False), copy all elements of
Temp() to Cellz().
'If Negflag is False but BigFlag is True, copy only elements that are
smaller than Targett#.
bbamp; = RngCntamp; - 1
RngCntamp; = -1
For aaamp; = 0 To bbamp;
If (BigFlag = True) And (NegFlag = False) Then
If (Temp(aaamp;).Nbr lt;= Targett#) And (Temp(aaamp;).Nbr lt;gt; 0) Then
RngCntamp; = RngCntamp; 1
ReDim Preserve Cellz(RngCntamp;)
Cellz(RngCntamp;).Addr = Temp(aaamp;).Addr
Cellz(RngCntamp;).Nbr = Temp(aaamp;).Nbr
End If
Else
If Temp(aaamp;).Nbr lt;gt; 0 Then
RngCntamp; = RngCntamp; 1
ReDim Preserve Cellz(RngCntamp;)
Cellz(RngCntamp;).Addr = Temp(aaamp;).Addr
Cellz(RngCntamp;).Nbr = Temp(aaamp;).Nbr
End If
End If
Next aaamp;
'Set Kount@ and SolnNbramp; to zero.
Kount@ = 0
SolnNbramp; = 0
'First call to KS() starts the chain of recursive calls. The For..Next loop
starts a new chain every time
'the previous chain returns a solution or False (no solution). Each new
chain starts one element farther in
'Cellz(), to ensure that a different solution, if any, will be found.
However, this means that the first
'element in Cellz() can only be in 1 solution, the 2nd element can only be
in 2 solutions, etc. So, we are
'still not finding every possible solution.
For bbamp; = 0 To (RngCntamp; - 1)
SolnCntamp; = -1
If KS(Cellz(bbamp;).Nbr, bbamp; 1) Then
SolnNbramp; = SolnNbramp; 1
SolnCntamp; = SolnCntamp; 1
ReDim Preserve Soln(SolnCntamp;)
Soln(SolnCntamp;).Addr = Cellz(bbamp;).Addr
Soln(SolnCntamp;).Nbr = Cellz(bbamp;).Nbr
'Add a new worksheet to the current workbook at the end.
If SolnNbramp; = 1 Then
Worksheets.Add.Move After:=Worksheets(Worksheets.Count)
SolnRowamp; = 1
Else
'Find the last row with data in column A.
Cells(65535, 1).Select
Selection.End(xlUp).Select
Selection.Offset(4, 0).Select
SolnRowamp; = Selection.Row
End If
'Stop before hitting the last row of the worksheet amp; abending.
If (SolnCntamp; SolnRowamp;) gt; 65500 Then
MsgBox quot;Can't fit all the solutions on the sheetquot;,
vbExclamation, quot;Errorquot;
Exit Sub
End If
'List the elements in Soln(), which make up the solution.
For aaamp; = 1 To SolnCntamp;
ActiveSheet.Cells(aaamp; SolnRowamp; 2, 1).Value =
Soln(aaamp;).Addr
ActiveSheet.Cells(aaamp; SolnRowamp; 2, 2).Value = Soln(aaamp;).Nbr
'Add some headings also.
Cells(SolnRowamp;, 1).Value = Targett#
Cells(SolnRowamp;, 2).Value = quot; = Targetquot;
Cells(SolnRowamp; 2, 1).Value = quot;Cellquot;
Cells(SolnRowamp; 2, 2).Value = quot;Valuequot;
Next aaamp;
End If
'Clear the array before the next iteration.
ReDim Soln(0)
Next bbamp;
'Find the last row with data in column A. 4 rows down, summarize the results.
If SolnNbramp; gt; 0 Then
Cells(65535, 1).Select
Selection.End(xlUp).Select
Selection.Offset(4, 0).Select
Selection.Value = SolnNbramp; amp; quot; solutions were found. KS function was
called quot; amp; Kount@ amp; quot; times.quot;
End If
'Tell user we are done. Summarize results.
MsgBox SolnNbramp; amp; quot; solutions were found. KS function was called quot; amp;
Kount@ amp; quot; times.quot;, vbInformation, quot;Done!quot;
Exit Sub
KSerr1:
If Err.Number lt;gt; 0 Then
msg101$ = quot;Error # quot; amp; Str(Err.Number) amp; quot; was generated by quot; _
amp; Err.Source amp; Chr(13) amp; Err.Description
MsgBox msg101$, , quot;Knapsack errorquot;, Err.HelpFile, Err.HelpContext
End If
End Sub

Public Function KS(yy As Double, xx As Long) As Boolean
'My own recursive and iterative algorithm for the classic knapsack
programming problem.
'yyamp; is the cumulative total tested against the target number in this call,
and passed to the next call
'increased by the next element of Cellz().
Dim nn As Long
'Call DoEvents so the screen can refresh, etc.
DoEvents
'Add 1 to Kount every time function is called.
Kount@ = Kount@ 1
'Start a loop to test all remaining values of Cellz[xx] from this point in
the solution chain.
nnamp; = xxamp;
Do While nnamp; lt;= RngCntamp;
If (yy# = Targett#) Then
'Found a solution in this call! Increase Soln() and save info about the last
element of Cellz() that was
'tried (nnamp;, which should always be the same as xxamp; at this point in the
function).
SolnCntamp; = SolnCntamp; 1
ReDim Preserve Soln(SolnCntamp;)
Soln(SolnCntamp;).Addr = Cellz(nnamp;).Addr
Soln(SolnCntamp;).Nbr = Cellz(nnamp;).Nbr
'Return True to the calling function.
KS = True
Exit Function
ElseIf (yy# gt; Targett#) Then
'yyamp; in this call exceeds the target number. Return False to the calling
function.
KS = False
Exit Function
'yyamp; is still less than the target number. Call KS() again, adding the next
element in Cellz() to yyamp;
ElseIf (KS(yy# Cellz(nnamp;).Nbr, nnamp; 1)) Then
'The call to another element of Cellz() found a successful chain. Info about
that element of Cellz()
'has already been saved in Soln(). Now increase Soln() and store information
about the Cellz() element
'in this call that is one link earlier in the solution chain.
SolnCntamp; = SolnCntamp; 1
ReDim Preserve Soln(SolnCntamp;)
Soln(SolnCntamp;).Addr = Cellz(nnamp;).Addr
Soln(SolnCntamp;).Nbr = Cellz(nnamp;).Nbr
'Return True to the calling function.
KS = True
Exit Function
End If
nnamp; = nnamp; 1
Loop
KS = False
End Functionquot;spyshotquot; wrote:

gt;
gt; in column A i have a set of numbers. in column B i have a single number
gt; that is the sum of some (not all) of the numbers in column A. i dont
gt; know what numbers from column A will equal the number in column B, nor
gt; do i know how many are added together to do so. but i do know that the
gt; number in column B is a combination of numbers from column A.
gt;
gt; its very important that i find a way to do this. any help would be
gt; greatly appreciated.
gt;
gt;
gt; --
gt; spyshot
gt; ------------------------------------------------------------------------
gt; spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
gt; View this thread: www.excelforum.com/showthread...hreadid=515054
gt;
gt;


B. R.Ramachandran ,

thank you so much, this worked!
i cannot thank you enough!!

spy--
spyshot
------------------------------------------------------------------------
spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
View this thread: www.excelforum.com/showthread...hreadid=515054
Tom Hutchins,

thank you for your reply and help. i will try this way as well. i
really appreciate everyone's help...thanks!

spy--
spyshot
------------------------------------------------------------------------
spyshot's Profile: www.excelforum.com/member.php...oamp;userid=31781
View this thread: www.excelforum.com/showthread...hreadid=515054