CODEWITHSUNDEEP
javascriptpythonalgorithmsubset-sum
algorerhythm
algorerhythm

Reputation: 11

Algorithm calculate the smallest sum that a number fits into

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

Alternate phrasing:

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

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.

Upvotes: 1

Views: 769

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50787

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.

Upvotes: 0

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

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.

Upvotes: 2

Related Questions