Editorial for Juegos de Video
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 be the greatest production we can get by using the first games and by spending at most 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 , the problem of choosing which games to buy for console is a straightforward knapsack problem which we can solve with the recurrence given above. That is, for a given console , we can calculate for console 's games and that will tell us which of console '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 for console represents a different "console package" that we could purchase. At each iteration , we could choose to buy console and any of these packages for console, 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 step are the outputs to the dynamic program for the console. We solve this dynamic program and this gives us the optimal value over all consoles.
Comments