I was had a question about optimizing for the longest distance travelled.
Suppose there is a highway which we can use to travel for a specific distance based on a set of fee rules involving 3 types of tokens $x, y, z$. You are given a set amount of each type of tokens and The fee rules are of the following form and is asked to maximize the distance travelled,
\begin{align*} &30x's + 10y's + 10z's \to d_1km\\ &30x's + 10y's + 0z's \to d_2km\\ &30x's + 0y's + 0z's \to d_3km\\ &5x's + 0y's + 0z's \to d_4km\\ &5x's + 3y's + 3z's \to d_5km\\ &\vdots \end{align*} My initial thought was to order the distance travelled from largest to smallest and try to spend my tokens in that order, but I believe this will cause me to miss out on some edge deals that will enable me to go even further. I believe I've seen some mathematical concept to optmizing this type of problems, but I can't remember exactly what this is called. Any hints or pointers as to how to tackle this problem is greatly appreciated!
One approach would be to use linear programming.
I will provide a short example with the first two fee rules and I will let you generalize it. Let's say that you pay $t_1$ times the fee to cover distance $d_1$ and $t_2$ respectively for $d_2$. Our goal now is to maximize the following objective function: $$ t_1\cdot d_1 + t_2\cdot d_2$$ However, we must have enough tokens to pay the fee. Assume that you started with $B_x$ tokens of type $x$. You use $30t_1$ tokens for fee rule 1 and $30t_2$ for fee rule 2 for a total of $30 (t_1 + t_2)$. Thus we must restrict our solution with $30(t_1 + t_2) \le B_x$. Similarly, $10 (t_1 + t_2)\le B_y$ and $10t_2 \le B_z$.
Or in matrix form, with $F$ denoting the fee coefficients, \begin{align*} \max \quad &d^Tt \\ \text{subject to} \quad &{Ft \le B}\\ &t \ge 0 \end{align*}