# unbounded 0-1 knapsack problem with cooldown for each item

Given a set of spells, each with a cast-time(=weight) and a damage(=value), cooldown(time that is required to cast it again. If the spell has 10s cooldown and you casted it at 0s, you have to wait until 10s to cast it again), determine which spells to include in the collection so that the total cast-time is less than or equal to a given limit and the total damage is as large as possible. Here we are allowed to use unlimited number of instances of an spell.

the image description of the problem (this is an image by aaronfarr.I found it while searching about this problem)

The problem is almost same as typical unbounded 0-1 knapsack problem. The difference is after casting a spell you have to wait untill the cooldown is over to cast it again.

I've tried to find an appropriate algorithm to solve this, but I couldn't(Since I am not used to algorithm, I might just didn't know how to apply it to problem).

My question is : what is an appropriate algorithm to solve this problem and how to modify it to solve this.

• To check understansing: if spell Fireball has cast-time 5 s. and cooldown 12 s., and you cast it at 0 s., at 5 s. you can cast another spell, but you have to wait until 12 s. to cast another Fireball? Commented Dec 6, 2023 at 16:00
• @Jean-ArmandMoroni yes, that's exactly how cast-time and cooldown works. Commented Dec 7, 2023 at 4:26

Standard knapsack is best solved using DP (Dynamic Programming).
Here, standard knapsack would be using just cast-time and damage, and only one instance max of each spell. We would recursively fill a table, with cast-time from $$0$$ to $$N$$ seconds in rows, and spells in columns.

Here we can also use DP; however the state space is larger than usual, and it cannot be represented as a two-dimension table anymore.

State space includes:

• Current time.
• For each spell, number of seconds left before end of cooldown.

As usual, the algorithm consists in computing the best value (here: maximum damage) for each state, in a single pass without backtracking.

For example, supposing Fireball has cast-time $$5$$ s. and cooldown $$10$$ s.:

• Computing value for state "Time: $$22$$ s., Fireball: remaining $$3$$ s. cooldown, Frost bolt: $$0$$ s., Fire blast: $$0$$ s." is just copying value from "Time: $$21$$ s., Fireball: $$4$$ s., Frost bolt: $$0$$ s., Fire blast: $$0$$ s.".
• Computing value for state "Time: $$12$$ s., Fireball: $$10$$ s., Frost bolt: $$0$$ s., Fire blast: $$0$$ s." is taking value of "Time: $$7$$ s., Fireball: $$0$$ s., Frost bolt: $$0$$ s., Fire blast: $$0$$ s." and adding Fireball damage to that value.

The state graph is quite sparse. For some parameters, it may be possible to not take into account some actions, e.g. the "action" of doing nothing. But in full generality, this may be suboptimal, as it may be best to wait $$2$$ seconds more to be able to throw another Fireball, rather than immediately throwing a Frost Bolt that will take $$4$$ s. casting, and prevent us from casting a last Fireball before time's end.

The state space may combinatorially explode, depending upon the number of different spells you have, their cast-times and cooldown times. In which case you should go for heuristics.

These heuristics can be devised by studying the best sequences of spells. For sufficiently long timespans, these sequences should usually consist in periodic repetition of the same spell list, with only the ending changing. However there may be (I am not sure about this) parameters for which the length of the non-periodic part may be very long. So in any case, it is best to code the DP algorithm, and see how it works, before delving into heuristics.

• In solution with DP, do I have to calculate every case of cooldown for each second? e.g. (Time: 12s, Fireball : 10s, Frost bolt 0s, Fire blast 0s), (Time: 12s, Fireball : 9s, Frost bolt 0s, Fire blast 0s), ..., (Time 12s, Fireball : 0s, Frost, bolt 0s, Fire blast 3s), and so on. In contrast to standard knapsack which I could only think about two constraint(weight, items allowed to use) and then fill the 2D table, i cannot imagine how to fill the table or even how to draw the table(or any kind of visualization for this) Commented Dec 7, 2023 at 9:33
• @evol1102 You have to calculate all cases that are possible (and that may be part of an optimum sequence, but this may be difficult to say in advance). It will be more like a graph than a table. Commented Dec 7, 2023 at 13:53