patternMinor
Highest possible value of combinations of 5
Viewed 0 times
combinationspossiblevaluehighest
Problem
According to https://www.heroescounters.com/teampicker a Hero has a synergy value with another hero, Heroes of the Storm have 60+ heroes each one with a synergy value for example:
A Team in heroes of the storm have 5 heroes, and the full synergy of a team is calculated by the formula:
Explaining the formula: Each Synergy Value after the synergy of Hero 1 and Hero 2 is calculated by the Mean of that Hero with the rest of the team, When Hero5 is added up i got the synergy of the team summing all the values.
My Answer is, How can I find the Team with the greatest possible synergy given that formula, and how can I write the code to find it given the possibility there are 64 Heroes(approximately) without brute-forcing all all 64^5 combinations of heroes.
HeroID Synergy.With.HeroID Synergy.Points
1 2 97
1 3 95
1 4 94
45 1 2
45 2 11A Team in heroes of the storm have 5 heroes, and the full synergy of a team is calculated by the formula:
Team_total_synergy = Synergy_Points(Hero1 with Hero2) +
mean(Synergy_Points(Hero3 + Hero1) + Synergy_Points(Hero3 + Hero2)) +
mean(Synergy_Points(Hero4 + Hero1) + Synergy_Points(Hero4 + Hero2) + Synergy_Points(Hero4 + Hero3)
[And so on... till Hero5]Explaining the formula: Each Synergy Value after the synergy of Hero 1 and Hero 2 is calculated by the Mean of that Hero with the rest of the team, When Hero5 is added up i got the synergy of the team summing all the values.
My Answer is, How can I find the Team with the greatest possible synergy given that formula, and how can I write the code to find it given the possibility there are 64 Heroes(approximately) without brute-forcing all all 64^5 combinations of heroes.
Solution
I suggest you solve it with integer programming (you can download gusek for free for not too complicated computations).
Define a graph $G=(V,E)$, where $V$ is the set of heroes, and $E$ a link between two heroes, with their synergy value $s_{i,j}$
for $(i,j) \in E$.
Define, for $i \in V$, $X_i$ the boolean variable equal to 1 iff you take hero $i$
Define additional real positive variables $Y_{i,j}$ for the cost, which are equal to 1 in the final solution iff heroes $i$ and $j$ are selected.
You want to solve
$\max \sum_{(i,j) \in E} Y_{i,j}s_{i,j}$
such that $\sum_{i \in V}X_i = 5$
$\forall (i,j) \in E, Y_{i,j} \leq X_i $
$\forall (i,j) \in E, Y_{i,j} \leq X_j $
other formulations are possible. I like this one, since it only has $|V|$ boolean variables
If that does not work (too much computation time), try to modify some already existing algorithms to find cliques, such as the one from Tarjan and Trojanowski.
Sidenote, you are lucky that the number of heroes is limited by 5. Otherwise, it would be a maximum clique problem, which is NP-complete.
Define a graph $G=(V,E)$, where $V$ is the set of heroes, and $E$ a link between two heroes, with their synergy value $s_{i,j}$
for $(i,j) \in E$.
Define, for $i \in V$, $X_i$ the boolean variable equal to 1 iff you take hero $i$
Define additional real positive variables $Y_{i,j}$ for the cost, which are equal to 1 in the final solution iff heroes $i$ and $j$ are selected.
You want to solve
$\max \sum_{(i,j) \in E} Y_{i,j}s_{i,j}$
such that $\sum_{i \in V}X_i = 5$
$\forall (i,j) \in E, Y_{i,j} \leq X_i $
$\forall (i,j) \in E, Y_{i,j} \leq X_j $
other formulations are possible. I like this one, since it only has $|V|$ boolean variables
If that does not work (too much computation time), try to modify some already existing algorithms to find cliques, such as the one from Tarjan and Trojanowski.
Sidenote, you are lucky that the number of heroes is limited by 5. Otherwise, it would be a maximum clique problem, which is NP-complete.
Context
StackExchange Computer Science Q#76580, answer score: 2
Revisions (0)
No revisions yet.