There is an equation:
280a + 80b + 75c + 50d + 25e - 30f - 42g = R
a, b, c, d, e, f, g- those are modifiers. They're strictly positive integer values.
R- this is a solution range, the equation is valid as long as the result of its left side falls into that range.
The goal is:
- For each possible subset of the variable set find the smallest sum of modifiers values such that the result of the left side of the equation is within given solution range.
Subsets are defined by inclusion of modifiers. I.e., modifier can either
== 0 or
b, c, d, e, f, g == 0and
a > 0is 1st subset
a, c, d, e, f, g == 0and
b > 0is 2nd subset
c, d, e, f, g == 0and
a, b > 0is 3rd subset
Basically it's like counting in binary. Ergo there's a total of 128 subsets (technically 127 since a subset where all modifiers
== 0 isn't needed as a solution).
Note: I know that
e can replace
c, d modifiers as both of these are divisible by it, but I still need those as separate modifiers for the sake of unique permutations.
Basically, the solution range is the input and the result should be a list of all valid subsets with the smallest sum of modifiers
Here's an example of a valid result:
- Let the range we input be from -2 to -2
Here's a list of smallest solutions for a couple different subsets (not all possible) with just
b, c, d, e, f, g modifiers: https://imgur.com/a/ZlWeAlq (permutation == subset, I didn't use the correct terminology at the time).
Plugging these values in the equation will result in
-2 on every subset (assume
a modifier is 0, I didn't include it in my first solver).
I made a quick bruteforce solution in C# with a parallel loop just going over all possible values (within boundaries) until it finds all solutions, but it's painfully slow.
A couple algorithms I have considered:
Add 1 of each modifier and check if any individual "node" is a solution. Then add 1 of each modifier to each previous node and see if any of the new nodes are solutions.
I'll have to somehow optimize it to not check the same path multiple times since adding 2 modifiers in different order will lead to the same node
This grows really fast in terms of memory, so I'll have to limit it to some range of values within which I allow this "branching", and then I'll only allow addition of identical modifiers until that "branching range" is close enough to the solution range. Something like:
- if a solution range is smth like 500-550, I'll only allow modifiers with positive coefficients to be added to itself until the value on each node is within 100 of the solution range
Simplify an arbitrary working answer:
Calculate the minimum difference you can create given the selected modifier set
Calculate how many minimum differences added together it takes to get into a solution range which can give a large number of modifiers being used but its a working answer
Use a table to quickly simplify/neutralize the modifiers with each other until you get the minimum possible
Bruteforce, but with even more optimization:
- I could add the same range check to a bruteforce algorithm so that it only tries every combination within a given range, as well as remove some unnecessary repetitions (my current solution sucks quite hard)
Another hopefully decent optimization I can think of right off the bat is to remove impossible subsets for a given range at the very start.
For example, if a range is positive, then subsets where only
g or only
f, g modifiers are
> 0 will never be a valid answer since both of these have negative coefficients (can't ever reach a positive range by adding negative values).
So my question is, which algorithm, either from the ones that I thought of or from other existing algorithms that I didn't think of, would be able to quickly and efficiently solve this problem?
I have yet to try to implement any of these since I'm not sure whether they will be good at all and if there are any existing algorithms that would be much better than any of the things I could think of. My bruteforce solution still exists and, if needed, I can link it. It is terribly slow tho and definitely not worth comparison in its current form.