0

Given a set of numbers, find the minimum multiple sum that an arbitrary number fits into

  • number in the set can be used multiple times (or not at all) to achieve a "sum"
  • the set of numbers may be any positive decimal (i.e. 1, 4, 4.5 )
  • given/arbitrary number threshold can be any decimal (i.e. 5 )

Alternate phrasing:

  • Find the combination of multiples that a given number can fit with the smallest remainder

  • Find the smallest "sum" that a number can round up to

  • The actual numbers used in each combination themselves are unimportant to this specific challenge

    • Though this could be fun to work out, too ^

Goal is to find the minimum "sum" (either the exact or rounded-up total); however, I would be happy to explore/learn the other factors

Other solutions seem to work backwards from an exact sum

Algorithm for calculating number of fitting boxes

  • not exactly a min-change coin problem

Others say variants of subset sums problem

Naive pseudo thinking to problem-solve at the moment:

  1. Get multiples of each
  2. Progressively increment sums of combinations all the elements (/ combinations of multiples of the elements; not sure of the best way to do this )
  3. Stop when each sum-finder has passed over the given number (threshold)
  4. mod to compare the smallest remainder that has passed over the given number i. may not need this step depending on how the combinations were built up together/separately
  5. Sum found

Thinking there may be a mathematical solution for this or other obvious python examples

https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

Subset whose sum is the smallest sum over a specific threshold - I think this dynamic programming closely resembles the challenge here; however, am at a bit of a hurdle on how to proceed on progressively combining/multiplying (+memoizing) all the potential combinations of the elements upwards in a pragmatic way.

Does recursively subtracting backwards work well in this type of problem?

Sample test cases

  1. Set [1, 4, 4.5] with arbitrary number 5; least sum = 5 (4 + 1)
  2. Set [1, 4, 4.5] with arbitrary number 5.1; least sum = 5.5 (4.5 + 1)
  3. Set [20, 40, 9001] with arbitrary number 88; least sum = 100 (40 + 40 + 20 or 20 + 20 + 20 + 20 + 20, or etc)
  4. Set [20, 40, 9001] with arbitrary number 145; least sum = 160 (40 + 40 + 40 + 40 or 20 + 20 + 20 + 20 + 20 + 20 + 20 + 20, or etc)
  5. Set [20, 40, 9001] with arbitrary number 9000; least sum = 9000 (40 * 225, etc, I think)
  6. Set [20, 40, 9001] with arbitrary number 9001; least sum = 9001 (9001, to exemplify cases with strange non-divisible components, given an arbitrary set)
  7. Set [20, 40, 9001] with arbitrary number 18002; least sum = 18002 (9001 + 9001)
  8. Set [100, 300, 420] with arbitrary number 101; least sum = 200 (100 + 100)
  9. Set [100, 300, 420] with arbitrary number 398.001; least sum = 400 (300 + 100)
  10. Set [100, 300, 420] with arbitrary number 404; least sum = 420 (420)

Thank you for any additional context, pointers, or simple pseudocode solutions you can help with.

algorerhythm
  • 1
  • 1
  • I would start by simplifying it, converting the problem into an integer problem: If a value is a non-integer, represent it as a fraction. Then multiply all values, including the desired result, by the LCM of the denominators. Then take the GCD of all of the values. If it doesn't divide the desired sum, then no exact solution exists. If it does divide it, then an exact solution *may* exist. It would definitely exist if negative multipliers were allowed. But since it seems that they aren't, it may not exist. – Tom Karzes Jun 17 '21 at 23:12
  • Should the least sum be 200 instead of 300 in the 8th test case? – hilberts_drinking_problem Jun 17 '21 at 23:14
  • @hilberts_drinking_problem nah because any of the values can be used 0 to many times, so if he can do it in 1 values its fine – Ryan Jun 17 '21 at 23:15
  • @Ryan I think using 100 twice leads to a smaller remainder than using 300 once. – hilberts_drinking_problem Jun 17 '21 at 23:16
  • 1
    @hilberts_drinking_problem you are correct, I explained how you were right and then proceeded to say otherwise lol – Ryan Jun 17 '21 at 23:16
  • Thanks for the proofread @4585963 [hilberts_drinking_problem](https://stackoverflow.com/users/4585963/hilberts-drinking-problem) 16109219 [Ryan](https://stackoverflow.com/users/16109219/ryan) Felt precarious as I was writing them. Also will update the test cases to a _numbered_ list – algorerhythm Jun 18 '21 at 00:03
  • [@5460719](https://stackoverflow.com/users/5460719/tom-karzes) So a good simplification approach would be to calculate the factors for the exact solution first? and then proceed about an inexact solution (I think an inexact solution will always exist in our cases, and will likely represent most of the intended inputs since we want to **round up to the next sum of multiples**) – algorerhythm Jun 18 '21 at 00:06
  • Are the following relevant (or even exact) problem domain? To get something working, it sounds like: 1. Combine everything (sum somehow, Knapsack)! 2. Sort 3. Keep searching through until you find the threshold tipping point 4. Job done 5. Try to optimise the mess. https://stackoverflow.com/questions/17923931/algorithm-to-find-elements-best-fitting-in-a-particular-amount [https://stackoverflow.com/questions/16022205/how-do-i-find-the-closest-possible-sum-of-an-arrays-elements-to-a-particular-va/16023064#16023064](https://stackoverflow.com/a/16023064/16256485) Different phrasing Add max – algorerhythm Jun 18 '21 at 00:24

2 Answers2

1

This may not be an algorithm per se, but you can use mixed integer programming to solve this problem. Here is an example using PuLP in Python:

import pulp

def solve(lst, target):
  # define a minimization problem
  prob = pulp.LpProblem("CombProb", pulp.LpMinimize)
  # vars[i] counts the number of time lst[i] is used in an optimal solution
  vars = pulp.LpVariable.dicts("count",  range(len(lst)), lowBound=0, cat="Integer")
  # define the objective
  prob += sum(vars[i] * lst[i] for i in range(len(lst)))
  # define the constraint
  prob += sum(vars[i] * lst[i] for i in range(len(lst))) >= target
  # solve the problem and check termination status
  assert prob.solve() == 1
  # return the objective value and involved list elements
  return prob.objective.value(), {lst[i]: vars[i].varValue for i in range(len(lst))}

tests = [
#   (lst, target, solution)
    ([1, 4, 4.5], 5, 5),
    ([1, 4, 4.5], 5.1, 5.5),
    ([20, 40, 9001], 88, 100), 
    ([20, 40, 9001], 145, 100),
    ([20, 40, 9001], 9000, 9000),
    ([20, 40, 9001], 9001, 9001),
    ([20, 40, 9001], 18002, 18002),
    ([100, 300, 420], 101, 200),
    ([100, 300, 420], 398.001, 400),
    ([100, 300, 420], 404, 420),
]

for i, (lst, target, sol) in enumerate(tests, start=1):
  res = solve(lst, target)[0]
  if res == sol:
    continue
  else:
    print(f"Error in case {i} with expected solution {sol} and computed solution {res}")

There seems to be an error in test case 4, but the other test cases pass.

hilberts_drinking_problem
  • 11,322
  • 3
  • 22
  • 51
  • Thank you for the well-annotated solve with mixed-integer linear programming. Gives me a lot of new concepts to learn about for this technique. Is the `PuLP` library the most accessible way to start diving into this? Thanks for catching the test case 4 typo as well - amended. Looking into the docs—`CombProb` text naming refers to Combinatorics Probability condition? Minimisation. Enumerates first and then optimises down until a condition is met? How exhaustively does it build up combinations - is there a soft/hard limit I should implement when thinking about similar probs? – algorerhythm Jun 19 '21 at 06:52
  • @algorerhythm If you want to learn how to use solvers, examples in PuLP could be a good start. You can also check out [Pyomo](https://pyomo.readthedocs.io/en/stable/) or [JuMP](https://jump.dev/JuMP.jl/stable/). Modern solvers tend to be very complex and it may be hard to tell how the solution is computed; "CombProb" is a random name I made up, loosely standing for "Combinations Problem". – hilberts_drinking_problem Jun 20 '21 at 00:23
0

I haven't thought through the efficiency at all, but a naive implementation seem pretty simple to write:

const {ceil, min} = Math;
const range = (lo, hi) => [... Array (hi - lo + 1)] .map ((_, i) => i + lo);

const minMult = ([n, ...ns], t) => 
   ns .length == 0 
    ? n * ceil (t / n)
    : min ( ...range (0, ceil (t / n)) .map (k => k * n + minMult (ns, t - k * n)));

[
  [[1, 4, 4.5], 5],
  [[1, 4, 4.5], 5.1],
  [[20, 40, 9001], 88],
  [[20, 40, 9001], 145],
  [[20, 40, 9001], 9000],
  [[20, 40, 9001], 9001],
  [[20, 40, 9001], 18002],
  [[100, 300, 420], 101],
  [[100, 300, 420], 398.001],
  [[100, 300, 420], 404]
] .forEach (
  ([ns, t]) => console .log (`minMult ([${ns.join(', ')}], ${t}) //=> ${minMult(ns, t)}`)
)
.as-console-wrapper {max-height: 100% !important; top: 0}

We recur on the length of the array. When we have only one number, then the answer is simply the smallest multiple of that number no larger than the target. Otherwise we take each multiple of our first number up through smallest multiple no larger than our target, and then recur on the remaining numbers and the uncovered portion of our original number, adding the results together.

JS doesn't have a range function, so we have to include our own. This version is simpler than Pythons, offering no step parameter and including the last value rather than stopping just short of it.

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103