I got an interesting question from my girlfriend last week:
Given I have a list of numbers, I want to select a subset of numbers that added up matches closest to a specific (positive) value.
Let me give a simplified example to explain what she was asking for:
If our list is [12, 79, 99, 91, 81, 47] and the expected value is 150, it should return [12, 91, 47] as 12+91+47 is 150.
If our list is [15, 79, 99, 6, 69, 82, 32] and the expected value is 150 it should return [69, 82] as 69+82 is 151, and there is no subset whose sum is 150.
This turns out to be known as the Subset sum problem and is a computational hard problem to solve. Luckily the list of numbers she needs to work with is quite small (about 50 numbers) and we can easily brute force this.
Today I want to show you how we can tackle this problem in Excel using the Solver add-in.
Activate the Solver Add-In:
- Go to the "File" tab.
- Click on "Options."
- In the Excel Options dialog box, click on "Add-Ins."
- In the "Manage" box at the bottom, select "Excel Add-ins" and click "Go."
- In the Add-Ins box, check "Solver Add-in" and click "OK."
Enter the data:
- Enter your list of values in a column, for example A1:A41
- Setup a second column B1:B41 that can be used by the Solver add-in
- In B42 we put the following formula =SUMPRODUCT(A1:A41, B1:B41)
- This will do the following calculation A1*B1+A2*B2+…
- By allowing Solver to change the values in column B to 1 or 0 we can create different combinations
- In B43 we add our target value
- IN B44 we put =ABS(B43-B42)
Set Up Solver:
- Go to the "Data" tab.
- Click on "Solver" in the "Analysis" group.
- Set the "Set Objective" box to our target cell $B$44
- Set the “Equal To” to Min to to look for the minimum value in $B$15 (to either give you an exact solution with no difference, or closest solution with smallest possible difference)
- In the "By Changing Cells" box, select the list of values in the B column $B$1: $B$41
- Constraint solver so that B1:12 must be binary (ie 1 or 0)
- In “Options” we configure Solver to only run for 1 minute
Running Solver:
- Click on “Solve” to allow Solver to run.
- You can stop the calculation at any time by hitting ESC.