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.
Labels:

Popular posts from this blog

Podman– Command execution failed with exit code 125

After updating WSL on one of the developer machines, Podman failed to work. When we took a look through Podman Desktop, we noticed that Podman had stopped running and returned the following error message: Error: Command execution failed with exit code 125 Here are the steps we tried to fix the issue: We started by running podman info to get some extra details on what could be wrong: >podman info OS: windows/amd64 provider: wsl version: 5.3.1 Cannot connect to Podman. Please verify your connection to the Linux system using `podman system connection list`, or try `podman machine init` and `podman machine start` to manage a new Linux VM Error: unable to connect to Podman socket: failed to connect: dial tcp 127.0.0.1:2655: connectex: No connection could be made because the target machine actively refused it. That makes sense as the podman VM was not running. Let’s check the VM: >podman machine list NAME         ...
Read more

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.
Read more

Cache stampede: when our cache turned against us

While investigating some performance issues, we ran into an ASP.NET Core API that cached a fairly expensive aggregation query for 60 seconds. Under normal load, that was fine: one request rebuilds the cache, everyone else reads from it. Under peak load, dozens of requests would arrive in that same expiry window, all see a cache miss, and all fire the same expensive query in parallel. The database didn't like that. That was the moment when our caching layer stopped helping and started hurting. A burst of requests comes in at the same time, all miss the cache, and all go hammer the database or the downstream API at once. That's a cache stampede . The cache was supposed to protect our backend, and for a few hundred milliseconds it did the opposite. Why this happens IMemoryCache.GetOrCreate (and its async sibling) looks like it protects you, but it doesn't add any locking on its own. Look at the naive version: public async Task<Report> GetReportAsync(string key) ...
Read more