1
$\begingroup$

I have been puzzled by the following question on an exam for quite a while: given a set of monsters with their health and attack damage (per second), design an algorithm that minimizes your overall damage received given that you can do one damage to one monster each second. Note: all monsters that are alive attack simultaneously, and the game ends only when all monsters are killed.

Since a greedy algorithm is not going to work, my guess is that there might be a dynamic programming solution to it. The DP algorithms we covered are the knapsack type of problems that are more or less in the form of subset selection, where the only decision made is to determine whether to include the current element in the set or not. However, the problem posted here is about the ordering of the elements (the order I attack the monsters). So it seems to me knowing the optimal solution to a subproblem of any kind would not help me obtain the solution to a larger problem.

I would appreciate hints on how to think about this problem.

$\endgroup$
0