CodeChef Problem Code: TSHOP (PART-1)

Link to problem statement: https://goo.gl/6Gfvxy

Before going ahead, try to think about the solution to this problem. Note that thinking about a solution doesn't require coding out your solution, just think about the approach. This is very important because if you'll think on your own and come up with a solution only then will you be able to analyze your algorithm and optimize it and you'll also feel great if you successfully come up with a solution, no matter whether it's optimal or not. When you are done with this step, your are good to move ahead.

After going through the problem statement, we are asked to optimize (maximize) something (calories). Take a note here that most of the optimization problems (either minimize or maximize) can be solved efficiently using Dynamic Programming. So, try to think whether the problem can really be solved using Dynamic Programming. For that purpose, try to identify overlapping sub-problems and optimal substructure in the given problem. If you identified these properties, move to Part-2 of this tutorial where we discuss the algorithm for the same. If you are still confused as why to solve this problem using dynamic programming, keep reading.

1. Overlapping sub-problems:
For each toffee, there are two possibilities, we either buy the toffee or we don't buy the toffee. Consider a recursive function T which takes parameters as N and B i.e. T(N, B) and returns maximum calories for given N and B. Now, T(N, B) is our main problem to be solved. We solve T(N, B) by dividing it into sub-problems. There will be two sub-problems for T(N, B) as given below:
a. T(N-1, B), if we don't buy the current toffee the budget won't be affected.
b. T(N-1, B-1), if we buy the current toffee, budget will be decremented by price of current toffee (for simplicity, consider price as 1 for all toffees and hence B-1).
Each sub-problems will then be divided into further sub-problems. To depict this, consider T(3, 2) as depicted in the figure below:



The RED nodes denote the overlapping sub-problems and hence this problem satisfies the over-lapping sub-problems property

2. Optimal Substructure:
To find maximum calories gained in budget B, we need to find maximum calories gained in budget B-1 and so on. We notice that optimal solution to the sub-problems contribute to the optimal solution of the given problem and hence it also satisfies the optimal substructure property and therefore the problem can be solved using Dynamic Programming.

Complete algorithm for the above problem is discussed in Part-2 of this tutorial for this problem.

Comments

Popular Posts