1

I have a range of values ( 5 - 19), and each value occurs a different number of times (eg 5 - 2x, 6 - 2x, 7 - 5x, etc.).

I've found various combination calculators on the web, but they are limited in certain ways. Either they don't find a given sum and just list all possible combinations, or they list all combinations for a given sum but don't allow specifying each value's occurrence.

Any tips/suggestions?

Thanks, Pat

Edit: I would also like to specify that the "sample size" equals 3, eg these combinations of 3 values equals 40.

Edit 2: After further reflection, I think I can refine my question a bit more.

I have 80 objects in total, and each is assigned a value ranging from 5 - 19. I have multiple objects of each value. I would like to know the combinations of these 80 objects to equal 40, limiting each combination to 3 or 4 objects, and limiting the combinations by the occurrence of each value.

Improve this question
7
  • 1
    Welcome to Web Applications Stack Exchange. This sounds like a variation of the Knapsack problem. There is no known efficient algorithm to give an optimal solution in the general case. A good enough solution may be possible, but that depends on many details. Consider sharing a publicly editable sample spreadsheet with realistic-looking data, and showing your hand-entered expected results there.
    – doubleunary
    Commented Dec 22, 2021 at 13:15
  • docs.google.com/spreadsheets/d/… Do you mean something like this? Each cell is an individual object, and is the actual data I'm working with. Let me know if you need any other info.
    – Pat
    Commented Dec 23, 2021 at 1:34
  • Hi and welcome. Your spreadsheet is a great start, but @doubleunary also asked that you [show] your hand-entered expected results. Would you please add this to your spreadsheet.
    – Tedinoz
    Commented Dec 23, 2021 at 6:29
  • Google has a product called OR-Tools - open source software for combinatorial optimization. The documentation includes a worked guide on The Knapsack Problem. The main hiccup that I can see is that it relies on Python, C++, Java or C# libraries. No JavaScript here and no example of a link to Google Sheets.
    – Tedinoz
    Commented Dec 23, 2021 at 6:37
  • Pat, have you read How do you automatically add values in an optimal order based on a criteria? on Google Docs Editors Help? In that case, the OP said After some deliberation, using Google sheets to do what I wanted to may not be the best solution. The alternative is probably to program my own tool to do this or look for other ready-made tools.
    – Tedinoz
    Commented Dec 23, 2021 at 6:49

1 Answer 1

Reset to default
1

You want to solve a subset sum problem, which is a variation of the knapsack problem.

The problem is NP-complete and there is no known efficient algorithm to give an optimal solution in the general case.

A good enough solution is possible in many cases, but if the sample spreadsheet you shared is realistic, I would say that the subsets you want cannot practically be calculated using plain vanilla spreadsheet formulas.

To understand why, see the new 'Simple subsets' sheet in your sample spreadsheet. It finds 153 different ways to combine exactly three terms so that their sum is 40 (including duplicates like 05 + 17 + 18 and 05 + 18 + 17).

The example is very simplistic, and does not take the number of available terms into account. It uses these formulas:

=query( unique( flatten( transpose(Sheet1!A1:O4) ) ), "where Col1 is not null limit 1000", 0 )

=arrayformula( unique( query( { flatten( trim(A2:A16) & " + " & transpose(trim(A2:A16)) ), flatten( A2:A16 + transpose(A2:A16) ) }, "where Col2 <= 40 order by Col2 asc limit 1000", 0 ) ) )

=arrayformula( unique( query( { flatten( trim(C2:C226) & " + " & transpose(trim(A2:A16)) ), flatten( D2:D226 + transpose(A2:A16) ) }, "where Col2 = 40 order by Col1 asc limit 1000", 0 ) ) )

To get a workable solution, you may want to use a proper combinatorial optimization package instead of a spreadsheet.

Improve this answer
1
  • 1
    doubleunary, you've been very helpful, I'm grateful. Your insight into the problem I presented was indeed very educational. As stated in my response to Tedinoz, I think I'm asking too much and overly complicating a not-very-serious task. Sorting through the combinations presented by the afore-mentioned web calculators is tedious and annoying, but not particularly problematic. Thanks again to both of you for your time, I do appreciate it. Hope you both enjoy the holiday season!
    – Pat
    Commented Dec 23, 2021 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.