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]

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 c

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)$.

StackExchange Computer Science Q#108820, answer score: 2