So I've got a type of generic question about a topic I'm not sure how to word (so I struggled to find it online) but I'll give a specific example first to help describe it.
Consider you have $30$ characters, each with a score in $6$ different categories? Is there some mathematics method to help work out which characters in which category yields the highest overall sum? I'm proposing to code an algorithm to do this so I'll refer to the first character as character $0$ and the last character as character $29$. Also, I wasn't sure which Stack Exchange site to post this question on, I'm sure there's some mathematical theory to benefit me, I just don't know what it would be called.
Eventually, I want to get up to $4$ characters in each of the $6$ categories. So far I've managed to do it by brute force (in reasonable time) for only the first $4$ categories or so, that is trying all of $(0,0,0,0)$ through to $(29,29,29,29)$ and ignoring any coordinate with some repeating integer. Clearly using brute force for the $16$ characters would result in going through $\frac{30!}{14!}\approx 3.04 \times 10^{21}$ from $M_{1 \times 16}(0)$ through to $M_{1 \times 16}(29)$, again ignoring any coordinate with a repeating integer. Not shockingly, way too many numbers for my computer to find a maximum in.
And then by working out a running maximum and the maximum score in each category, I was able to significantly make my code more efficient by dismissing any (say) first $i$ coordinates such that adding the absolute maximum score in each of the remaining categories would still make it less than the largest actual (non-repeating) combination sum found yet. So say that $(0,5,7)$ had a total so far of $1000$ and the sum of the absolute largest scores in each of the remaining $3$ categories is $1000$, but I've already found an actual (non-repeating) sum of $2100$, then I'd dismiss any coordinates $(0,5,7,x,y,z)$ with $x,y,z\in\{1,2,3,4,6,8,9,...,29\}$ and $x\neq y\neq z \neq x$.
This worked in reasonable time for $6$ characters ($1$ in each category) and then further for $8$ characters ($3$ characters for the first category and $1$ character in each of the remaining categories). Also, note that as I get higher with the number of characters it becomes impossible for me to verify that my code is yielding the largest possible actual (non-repeating) sum.
This is similar to having $>4$ swimmers each with a personal best time in each of the $4$ swimming strokes and try to work out the medley relay (one swimmer for each stroke) with the fastest overall time. I've recently started learning graph theory including proper vertex colouring where you can arrange (say) exams in a way with the least possible number of time slots so that no student has two exams at the same time. This question seems somewhat similar.
So does anyone know if this is a common type of question? In which case I'd appreciate a simple point in the right direction. Or rather could someone give me some tips on answering this specific question more efficiently.
This can be solved using integer linear programming, for which there are a large number of exact and approximation algorithms. Number the people $0$ to $29$ and the categories $0$ to $5$. Let $x_{i,j}$ be a variable which is $1$ if you put person $i$ in category $j$, and zero otherwise. You want to maximize $$ \sum_{i,j}s_{i,j}x_{i,j} $$ where $s_{i,j}$ is the score in the $j^{th}$ category of person $i$ (thanks to RobPratt for catching a mistake I had here). This is constrained by $$ \sum_{i=0}^{29}x_{ij}=4\qquad \text{for each }j\in \{0,\dots,5\}\\ \sum_{j=0}^{5}x_{ij}\le 1\qquad \text{for each }i\in \{0,\dots,29\}\\ x_{i,j}\ge 0 $$ The first batch of constraints ensure that there are $4$ people chosen for each category, and the second batch ensures each person is put in at most one category.