Find combinations of 3 values that add to final value

Question

So I only took math up to high school level and a bit during uni, but I do code a lot and can figure out a lot of algorithms and formulas to get what I want, but this stumped me...

I never had to figure out a formula/algorithm that gives this specific answer I want, and I mostly try to solve it by trial and error manually, but I want to automate this process.

---

I have this formula: 9x + 5y + 3z = w

Being that x, y, and z must all be non-negative integers. I have the value of w, and I want to find the combination of x, y, and z that sum to the lowest number possible. So x + y + z needs to be the lowest number possible, while giving me the w result.

For example, if I want w = 30, I know that the best combination is x = 3, y = 0, z = 1, which results in 9*3 + 5*0 + 3*1 = 30

This has a x + y + z = 4. I know other possible combinations will have a higher sum. Another possible combination is simply x = 0, y = 6, z = 0, but that sums up to x + y + z = 6.

---

This is basically the context:

I have the option of 3 actions, each gives a different amount of points. One gives 3 points, one gives 5 points, and the last gives 9 points. I can only do 1 action every few hours, and I want to optimize the time it takes to get to a certain amount of points. Sometimes I can go OVER the amount of points I need (like I need at least 40 points, but if 45 is quicker, I can go over to 45), but sometimes I need the exact amount (I need exactly 40 points, so I need to do 3x the 9 points action, 1x the 3 points action, and 2x the 5 points action), so this is another var I could take into account...

I do accept brute-force coding! I just want to make it more optimized as to at least finding the different combinations that give me that amount of points.

---

I also don't know about math terms and what kind of equation this is, so I'll leave this untagged and ask for help to tag it. I think it is a linear equation, but I am not sure...

Answer 1

Brute force approach pseudocode:

First take an array $S=(0,0,0)$.

Check if $(x,y,z)=S$ satisfies the equation.

Declare an array $B$ as the set of all 3 digit non-zero binary numbers, ordered in ascending order of digital sum ($001, 010, 100, 011, 101, 110, 111$)

Now for each 3 digit binary number in $B$, do:

Split $b$ into a tuple $T$; like $010$ becomes $(0,1,0)$

Check if $(x,y,z)=S+T$ satisfies your equation

End for loop

Update $S$ by $S=S+(1,1,1)$ and repeat from the start of the for loop

Edit: I think that this method can quite easily be extended for more than 3 parameters

Answer 2

Directly, we can model this as an integer optimization model like so:

$$\min x + y + z$$ $$\text{Subject to:}\qquad\qquad\qquad\qquad\qquad\qquad$$ $$9x + 5y + 3z = w$$ $$x,y,z\in\mathbb{Z}^+ \text{ and $w$ is a constant, positive integer}$$

Since this is an integer single-constraint Knapsack problem, we can use the Simplex algorithm to find the optimal linear relaxed solution, and then branch-and-bound for the nearest optimal integer solution. This is slightly better than brute forcing, but for sufficiently more decision variables this can get computationally more exhausting, though this isn't comparably as bad as the multi-dimensional knapsack problem where we have more than one constraint. There are however different ways to solve single constraint knapsack problems: Ratio Method and Dynamic Programming

Depending on the language you are using, there are integer optimization solvers that can do this, for example in Python there is Scipy and DoCplex

Lastly, here is an online solver where you can see this in action with a linear solver, just use the following code:

var x >= 0, integer;
var y >= 0, integer;
var z >= 0, integer;

minimize summation: x + y + z;

#replace w with a constant integer of your choosing
subject to sum_of_points:   9*x + 5*y + 3*z ==  w;

end;

Answer 3

It can easily be shown that you only have to consider $y\in\{0,1,2\}$ and $z\in\{0,1,2\}$. Assume you have a solution $9x+5y+3z=w$ and $y\geq 3$. Then the cost is $x+y+z.$ We also have $$ 9x+5y+3z= 9(x+1) + 5(y-3) + 3(z+2) $$ So there is another solution with the same cost of $(x+1)+(y-3)+(z+2)=x+y+z.$ You can theoretically continue decreasing $y$ by $3$ (and simultaneously increasing $x$ by $1$ and $z$ by $2$) until $y\in\{0,1,2\}$ without changing the cost.

If you have a solution with $z\geq 3$, then $$ 9x+5y+3z= 9(x+1) + 5y + 3(z-3) $$ So you can continue decreasing $z$ by $3$ (and simultaneously increasing $x$ by $1$) until $z\in\{0,1,2\}$ - and you even reduce the cost.

Now you have to find $(y,z)\in\{0,1,2\}^2$ such that $5y+3z\equiv w\pmod 9.$ You have to set up the table for that only once. Try all combinations of $y$ and $z.$ $$ y=0,\;z=0\;\; \Longrightarrow\;\; 5y+3z = 0 \equiv 0\pmod 9 \\ y=0,\;z=1\;\; \Longrightarrow\;\; 5y+3z = 3 \equiv 3\pmod 9 \\ y=0,\;z=2\;\; \Longrightarrow\;\; 5y+3z = 6 \equiv 6\pmod 9 \\ y=1,\;z=0\;\; \Longrightarrow\;\; 5y+3z = 5 \equiv 5\pmod 9 \\ y=1,\;z=1\;\; \Longrightarrow\;\; 5y+3z = 8 \equiv 8\pmod 9 \\ y=1,\;z=2\;\; \Longrightarrow\;\; 5y+3z =11 \equiv 2\pmod 9 \\ y=2,\;z=0\;\; \Longrightarrow\;\; 5y+3z =10 \equiv 1\pmod 9 \\ y=2,\;z=1\;\; \Longrightarrow\;\; 5y+3z =13 \equiv 4\pmod 9 \\ y=2,\;z=2\;\; \Longrightarrow\;\; 5y+3z =16 \equiv 7\pmod 9 $$ Now you only have to look for the remainder when you divide $w$ by $9,$ take $y\in\{0,1,2\}$ and $z\in\{0,1,2\}$ from the "table" above and set $x$ such that you get the correct $w$.

Pseudo-code:

input w
bestY = (0,2,1,0,2,1,0,2,1)
bestZ = (0,0,2,1,1,0,2,2,1)
r = remainder(w,9)
y = bestY(r)
z = bestZ(r)
x = (w-5*y-3*z)/9
if x<0 
    Error "No solution"
else
    output x,y,z

Answer 4

Note: This answer has been heavily edited in the light of Reinhard's valid comments. It should be working OK now and gets correct solutions to exceptions like w= 19 (x,y,z)=(1,2,0) that Reinhard pointed out. This method is not strictly brute force, because it does not work by testing all possible permutations of x, y and z.

The code can be copied and pasted into an online Python IDE complier for testing.

This one gives full information for a given choice of w.

import math
w=x=y=z=r=points=xyz = 0
def no_exact_solution():
    global x,y,z,r
    print( "No exact solution. Under by ",r)
    points = x*9+y*5+z*3
    xyz = x+y+z
    print( "Nearest under solution: x = ",x,", y = ",y,", z = ",z,", Total points = ",points," for time x+y+z = ", xyz)
    if z>0: z-=1;y+=1
    elif y>0:y-=1;x+=1
    else:z+=1
w = int(input('Enter points target value (w): '))
x = math.floor(w/9);r = w - x*9 
if r > 0:
    y = math.floor(r/5);r = r -y*5
    if r > 0:z = math.floor(r/3);r = r - z*3
print()
if r == 1:
    if y>0:z+=2;y-=1;r = 0
    elif x>0:y+=2;x-=1;r=0
    else: no_exact_solution()
elif r == 2:
    if y>1:y-=2;x+=1;z+=1;r=0
    elif x>0:x-=1;y+=1;z+=2;r=0
    else: no_exact_solution()
points = x*9+y*5+z*3; xyz = x+y+z
if r==0:
    print( "Exact solution: x = ",x,", y = ",y,", z = ",z,", Total points = ",points," for time x+y+z = ", xyz)
else:
    print( "Nearest over solution: x = ",x,", y = ",y,", z = ",z,", Total points = ",points," for time x+y+z = ", xyz)
    excess = x*9+y*5+z*3-w
    print( "Over by ",excess)

This version tests all values of w from 0 to 1,000,000 but only prints out information on those values that do not have an exact integer value. It finds only 4 such values (w = 1,2,4,7) in that range.

Maybe there are no values of w>16 that do not have an integer solution?

import math
w=x=y=z=r=points=xyz=count = 0
def no_exact_solution():
    global x,y,z,r
    print( "No exact solution for w = ",w,". Under by ",r)
    points = x*9+y*5+z*3;xyz = x+y+z
    print( "Nearest under solution: x = ",x,", y = ",y,", z = ",z,", Total points = ",points," for time x+y+z = ", xyz)
    if z>0:z-=1;y+=1;
    elif y>0:y-=1;x+=1
    else:z+=1
def test():
    global x,y,z,r,xyz,w, points,count
    x = math.floor(w/9);r = w - x*9
    if r > 0:y = math.floor(r/5);r = r -y*5
    if r > 0:z = math.floor(r/3);r = r - z*3
    if r == 1:
        if y>0:z+=2;y-=1;r=0
        elif x>0:y+=2;x-=1;r=0
        else: no_exact_solution()
    elif r == 2:
        if y>1:y-=2;x+=1;z+=1;r=0
        elif x>0:x-=1;y+=1;z+=2;r=0
        else: no_exact_solution()
    points = x*9+y*5+z*3;xyz = x+y+z
    if r !=0 :
        count+=1
        print( "Nearest over solution: x = ",x,", y = ",y,", z = ",z,", Total points = ",points," for time x+y+z = ", xyz)
        excess = x*9+y*5+z*3-w;print( "Over by ",excess);print()
testrange = 1000000
for w in range(0, testrange):test()
print();print("found ",count," inexact solutions in ",testrange," tests")