Editorial for Juegos de Video


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Leonardo

This problem feels like a Dynamic Programming (DP) problem. Except for the need to buy the consoles, this is exactly a knapsack problem where the game prices GPj are the sizes of the items and production values PVj are the values of the items. The budget V is the size of the knapsack. If we ignored the need to buy the consoles, we could define the subproblems by letting  prod[j][c] be the greatest production we can get by using the first j games and by spending at most c \le V dollars. The recurrence is then:

prod[j][c] = max(prod[j-1][c], PV_j + prod[j-1][c - GP_j])

because with each new game i, we can either not buy it or we can buy it at a cost of GPi and get a value of PVi.

Next, note that once we've committed to buy a console i, the problem of choosing which games to buy for console i is a straightforward knapsack problem which we can solve with the recurrence given above. That is, for a given console i, we can calculate prod[j][c] for console i's games and that will tell us which of console i's games to buy for each budget.

The last step is that we need to choose which consoles to buy. Think of this as a knapsack problem on consoles, except that each console doesn't have a single cost and a single value: we can spend more or less on each console depending on which games we buy and we get correspondingly more or less production. Each prod[j][c] for console i represents a different "console i package" that we could purchase. At each iteration i, we could choose to buy console i and any of these packages for console i, or we could skip console i entirely. This gives us a knapsack dynamic program on consoles where the items we can put in the knapsack at the ith step are the outputs to the prod[j][c] dynamic program for the ith console. We solve this dynamic program and this gives us the optimal value over all consoles.


Comments

There are no comments at the moment.