Skip to main content

Find a subset from a set of values whose sum is closest to a specific value– Excel

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.

Popular posts from this blog

DevToys–A swiss army knife for developers

As a developer there are a lot of small tasks you need to do as part of your coding, debugging and testing activities.  DevToys is an offline windows app that tries to help you with these tasks. Instead of using different websites you get a fully offline experience offering help for a large list of tasks. Many tools are available. Here is the current list: Converters JSON <> YAML Timestamp Number Base Cron Parser Encoders / Decoders HTML URL Base64 Text & Image GZip JWT Decoder Formatters JSON SQL XML Generators Hash (MD5, SHA1, SHA256, SHA512) UUID 1 and 4 Lorem Ipsum Checksum Text Escape / Unescape Inspector & Case Converter Regex Tester Text Comparer XML Validator Markdown Preview Graphic Color B

Help! I accidently enabled HSTS–on localhost

I ran into an issue after accidently enabling HSTS for a website on localhost. This was not an issue for the original website that was running in IIS and had a certificate configured. But when I tried to run an Angular app a little bit later on http://localhost:4200 the browser redirected me immediately to https://localhost . Whoops! That was not what I wanted in this case. To fix it, you need to go the network settings of your browser, there are available at: chrome://net-internals/#hsts edge://net-internals/#hsts brave://net-internals/#hsts Enter ‘localhost’ in the domain textbox under the Delete domain security policies section and hit Delete . That should do the trick…

Azure DevOps/ GitHub emoji

I’m really bad at remembering emoji’s. So here is cheat sheet with all emoji’s that can be used in tools that support the github emoji markdown markup: All credits go to rcaviers who created this list.