Given 5 curves, find the maximum total you can get for each possible level Problem

Constraints


I have a collection of curves, $C$. It is a two dimensional array. The inner array contains rational numbers, where the next is greater or equal to the previous.

$$C_{k.i} = v\\
\{k \in \mathbb{Z}: 0 \le k \le 5\}\\
\{i \in \mathbb{Z}: 0 \le i \le 99\}\\
\{v \in \mathbb{N}: 0 \le v \le 1\}\\
C_{n.i} \le C_{n.j}\\
\{j \in \mathbb{Z}: i \le j \le 99\}
$$
I have $n$ levels.

$$\{n \in \mathbb{Z}: 0 \le n \le 5 * 99\}$$


Example

C = [[i / 100 for i in range(100)]] * 5
n = 20


Task

For a given $n$ split it into five non-negative integer indexes. Which are used to index each curve and sum the result to get the total, $t$.

$$
n = a + b + c + d + e\\
t = C_{1.a} + C_{2.b} + C_{3.c} + C_{4.d} + C_{5.e}$$

For each $n$ find the maximum $t$ for a given $n$. And what the values for $a$, $b$, $c$, $d$ and $e$ are.

Solution

The way I solved this was through brute force:


Build list of tuples to store the maximum, $o$.
These tuples are (total, list of products).
Find the value for all products of $a$, $b$, $c$, $d$ and $e$.
For each product find the total of the curves, $t$.


If $o_{n.0} = t$ append [(a, b, c, d, e)] to $o_{n.1}$.
Otherwise if $o_{n.0} \lt t$ set $o_{n}$ to (t, [(a, b, c, d, e)]).

Output $o$.


In Python this can be expressed as: (variable names correlate with the ones defined above)

import itertools


o = [(-1, [])] * 495
for prod in itertools.product(range(100), repeat=5):
    n = sum(prod)
    t = sum(c[i] for c, i in zip(C, prod))
    if o[n][0] == t:
        o[n][1].append(prod)
    elif o[n][0] &lt; t:
        o[n] = (t, [prod])


This runs in $ki^k$ time, which is rather slow.

Question

I think the performance can be improved by using caching or a fancy algorithm.
Can this algorithm's performance be reduced by an order of magnitude?





Ideas

I though running through all values of $n$ adding the highest value $v$ to a running total.
And adding the running total to the output.

This would run in $O(kn)$ time.

But this doesn't work correctly as if there are any curves that start off with a small gradient then the gradient increases to overtake all the other curves. It wouldn't be selected.



I thought about finding the maximum value a curve can be at the provided level.
Then running through output and the maximum curve from $n$ backwards to see if there are any other totals that are greater than the current one.

This seems like it might work, and might run in $O(n^2)$ time, which is significantly smaller than $O(ki^k)$.

However I think it has similar problems to the above solution that I can't think of yet.



I've thought about vectorizing the curve into, $l$, straight lines. I'm not sure what this complexity is, but I'll call it $v$.
From this it is easy to compare vectors to see which have greater starting points, and then a greater coefficient.
Precomputing the intersections, $s$, also allows you to know when to switch to a different vector efficiently.

I've not fully thought this through, but it seems like it could be something like $O((lk + s)n + (lk)^2 + v)$.
It's easy to achieve $O(n^4)$ running time: iterate over all possible values of $a,b,c,d$, set $e=n-a-b-c-d$, compute $C_a+C_b+C_c+C_d+C_e$, and keep the best one found so far.

You can achieve $O(n^3)$ running time and $O(n^2)$ space with a meet-in-the-middle algorithm:

Step 1. Create an empty hash table.  For each $d,e$ such that $d+e\le n$, add an entry to a hash table keyed on $d+e$ mapping to the value $C_d+C_e$; if it already has an entry for the key $d+e$, replace the existing entry if $C_d+C_e$ is larger than whatever was previously there, otherwise do nothing.  (Save the value of $d,e$ whenever you update the entry, too.)

Step 2. For each combination $a,b,c$ such that $a+b+c \le n$, look up the key $n-a-b-c$ in the hash table.  This gives you $d,e$ that maximizes $C_d+C_e$, subject to the requirement that $d+e=n-a-b-c$, i.e., that $a+b+c+d+e=n$.  Now compute $C_a+C_b+C_c+C_d+C_e$.  Keep the best combination you ever see.

You can achieve $O(n^2)$ time and space by keeping Step 1 above and replacing Step 2 with

Step 2'.  For each combination $a,r,s$ such that $a+r+s=n$, look up the key $r$ in the hash table to find $b,c$ such that $b+c=r$ and look up the key $s$ in the hash table to find $d,e$ such that $d+e=s$.  Compute $C_a+C_b+C_c+C_d+C_e$ and keep the best combination you ever see.  You can iterate over all such combinations $a,r,s$ by iterating over $a,r$ such that $a+r \le n$, then setting $s=n-a-r$.  There are $O(n^2)$ such combinations of $a,r,s$, and this algorithm does $O(1)$ work per combination, so the total running time is $O(n^2)$.