Member Avatar for dlh6213

I’m trying to find a way, either with Excel or another program, to find out what combination of numbers will equal a predetermined sum. I’ve tried Excel Help and the internet, and it appears possible, but all the examples are far more complicated than what I’m trying to do and they don’t seem to work for me. Here’s an example of what I’m trying to do:
If I have the following set of numbers:
1.00
1.50
2.00
2.30
2.90
5.30
5.40
6.30
6.90
7.40
7.80
8.30
9.50

I’d like to find out which combinations will total 9.6 and 9.7; the same number can be used multiple time (i.e. 1.00 eight times plus 1.5 = 9.5)

It seems like ?Solver in Excel should work for this, but I can’t get the results I want.

  • 3 Contributors
  • 5 Replies
  • 367 Views
  • 3 Years Discussion Span
  • Latest Post Latest Post by W2K5HHHXIT

Dani AI

Generated

Two practical ways to solve this in Excel: use Solver as an integer linear model to get a single feasible combination, or run a small VBA backtracker to enumerate every combination (the latter is what was suggesting with recursion). Solver is fine if you want “a” solution quickly; VBA is better if you want to list all possible solutions.

Solver (one solution)

  • Put your item values in one column and put adjacent cells for the unknown integer counts.
  • Create a cell for the difference: =SUMPRODUCT(values_range,counts_range)-target_cell.
  • In Solver set that difference cell to a Value Of 0, with the counts_range as decision variables.
  • Add constraints: counts >= 0 and Integer. Also add an upper bound such as counts <= INT(target/min_value) to keep the search finite.
  • Use the Simplex LP (and tick “Assume Linear Model”) since this is linear with integer variables. Solver returns one feasible combination quickly; repeat with extra constraints if you need different solutions.

VBA backtracking (enumerate all solutions)

  • Scale decimals to integers (multiply by 100) to avoid rounding issues.
  • Read values from a sheet, recurse through values trying 0..max copies of each value, and print solutions when the remaining sum hits zero.
  • This enumerates combinations (counts per value), not permutations, so 1+1.5 and 1.5+1 are treated the same.

Example VBA (put values in column A starting at A2 and the target in B1; results go to the Immediate window):

Option Explicit

Sub FindCombinations()
    Dim ws As Worksheet: Set ws = ActiveSheet
    Dim vals() As Long, n As Long, r As Long
    r = 2: n = 0
    Do While Trim(ws.Cells(r, "A").Value) <> ""
        ReDim Preserve vals(0 To n)
        vals(n) = CLng(ws.Cells(r, "A").Value * 100 + 0.5)
        n = n + 1: r = r + 1
    Loop
    If n = 0 Then MsgBox "No values found": Exit Sub
    Dim target As Long: target = CLng(ws.Range("B1").Value * 100 + 0.5)
    Dim counts() As Long: ReDim counts(0 To n - 1)
    RecurseFind vals, counts, 0, target
End Sub

Sub RecurseFind(vals() As Long, counts() As Long, idx As Long, rem As Long)
    Dim q As Long, maxQ As Long
    If rem < 0 Then Exit Sub
    If idx = UBound(vals) Then
        If rem Mod vals(idx) = 0 Then
            counts(idx) = rem \ vals(idx)
            Debug.Print FormatSolution(vals, counts)
        End If
        Exit Sub
    End If
    maxQ = rem \ vals(idx)
    For q = 0 To maxQ
        counts(idx) = q
        RecurseFind vals, counts, idx + 1, rem - q * vals(idx)
    Next q
    counts(idx) = 0
End Sub

Function FormatSolution(vals() As Long, counts() As Long) As String
    Dim i As Long, s As String
    For i = 0 To UBound(vals)
        If counts(i) > 0 Then
            If Len(s) > 0 Then s = s & " + "
            s = s & counts(i) & "x" & Format(vals(i) / 100, "0.00")
        End If
    Next i
    FormatSolution = s
End Function

Tips and caveats

  • Multiply values/target to integers (cents) to avoid floating errors.
  • Sort values descending before searching to prune faster.
  • Add an upper bound for counts to reduce runtime.
  • There may be many solutions — limit results or write them to a sheet rather than the Immediate window.
  • For very large inputs consider dynamic programming or a proper ILP solver.

This keeps ’s recursion idea but gives a ready-to-run VBA path inside Excel for enumerating all combinations.

Recommended Answers

All 5 Replies

Member Avatar for JamesCherrill

I doubt that you will find an off-the-shelf solution, nor will you find an easy one.
You need to traverse a tree with nodes for each value x1, x2, x3 etc.
Looks like a recursive algorithm.
How much do you really want a solution?

Member Avatar for JamesCherrill

If you're still interested...
Here's a little runnable demo I hacked up in Java to show how the recursive solution works:

    int[] values = {1, 2, 9, 3};
    int target = 8;

    tryValue(0, 0);

    // recursive algorithm to try all possible combinations of values and
    // multipliers that add up to the target.

    // LIFO history of steps leading to the current one...
    Deque<String> solution = new LinkedList<>();

    void tryValue(int valueIndex, int runningTotal) {

        if (valueIndex >= values.length) {
            return; // tried every value
        }

        int value = values[valueIndex]; // just for convenience
        int multiplier = 0;
        int newTotal;

        // keep trying multiples of this value until it exceeds taget...
        while ((newTotal = runningTotal + value * multiplier) <= target) {
            solution.push(multiplier + "x" + value);
            if (newTotal == target) {
                System.out.println(solution + " = " + target);
            } else {
                // try adding (multiples of) the next value....
                tryValue(valueIndex + 1, newTotal);
            }
            solution.pop();
            multiplier++;
        }

    }
Edited by JamesCherrill
Member Avatar for dlh6213

Thanks for the response! I was really hoping there would be an easy way to do this - preferably with Excel, but I guess not. Thanks for the suggestion; maybe I'll give it a go.

Member Avatar for JamesCherrill

I guess you could use Visual Basic for Applications (VBA) in Excel - my Java code is simple enough that you should be able to translate into vba without too much difficulty.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.