CodeChef Problem Code: TSHOP (PART-2)
Link to problem statement: https://goo.gl/6Gfvxy
After going through Part-1 of this tutorial, we are clear about our approach to solve the given problem, it's time to design an algorithm for the same. It's highly recommended to go through Part-1 of this tutorial before starting off with this one.
Recall the recursive approach that we discussed in the Part-1 when we were identifying over-lapping sub-problems. We had a function T with N and B as parameters and each problem was divided into two sub-problems. Now, we need to identify which of these two sub-problems provide the optimal solution for the problem. To avoid redundant computations and to easily compare and decide among the two sub-problems about which one provides an optimal solution to the problem, we maintain a 2-D matrix to store result for each sub-problem.
Now, what will be the size of this 2-D matrix?
Pretty simple. We are considering N and B for calculating the optimal solution. Hence, we create a 2-D matrix of size N*B but as B will start from 0, we will need a matrix of size N*(B+1). For a given N and given B, we store the optimal solution for the given N and B in table[N][B].
Assumptions:
1. price[N] : Array containing price of each toffee.
2. calorie[N] : Array containing calorie content for each toffee.
3. table[N][B+1] : Table to store optimal solution for all the sub-problems.
Algorithm:
STEP 1: For each toffee and each budget do (toffee = 0 to N-1 & budget = 0 to B):
If the current budget is less than price of the current toffee we don't buy the current toffee and hence maximum calorie we get will be one of the following:
1. If we only have one toffee i.e. current toffee:
Maximum calories will be 0 as we are left with no other toffees.
2. Else:
Maximum calories will be that of without buying the current toffee i.e. matrix[toffee-1][budget].
If current budget is greater than or equal to the price of the current toffee, the maximum calorie we can obtain will be one of the following:
1. If we only have one toffee i.e. current toffee, we buy the current toffee:
Maximum calories will be that of current toffee as we don't have any other toffees to consider.
2. Else:
Maximum calories will be maximum calories obtained by either buying the current toffee or not buying the current toffee. i.e. Max(table[toffee-1][budget], calorie[toffee] + table[toffee-1][budget - price[toffee]]).
STEP 2: print table[N-1][B]
As we are calculating solution for all the sub-problems and storing them in a matrix, the time and space complexity for the above algorithm is O(N*B).
Link to view/download code for the given problem: https://goo.gl/n7AZu3
NOTE:
Now if you notice carefully, this problem is very similar to standard 0-1 Knapsack problem that we encountered earlier in Dynamic Programming. If you're not familiar with the standard 0-1 knapsack problem, I'll highly recommend to read about it here: https://goo.gl/qck9o3
So, if you are able to identify and reduce the given problem into some standard problem, you can solve the given problem in a very similar way for solving that standard problem. Also, it saves a bunch of time if you have a good grasp of common standard problems.
Hope you liked the tutorial, for any suggestions or improvements, please comment in the comment section below. Thank you for reading.
After going through Part-1 of this tutorial, we are clear about our approach to solve the given problem, it's time to design an algorithm for the same. It's highly recommended to go through Part-1 of this tutorial before starting off with this one.
Recall the recursive approach that we discussed in the Part-1 when we were identifying over-lapping sub-problems. We had a function T with N and B as parameters and each problem was divided into two sub-problems. Now, we need to identify which of these two sub-problems provide the optimal solution for the problem. To avoid redundant computations and to easily compare and decide among the two sub-problems about which one provides an optimal solution to the problem, we maintain a 2-D matrix to store result for each sub-problem.
Now, what will be the size of this 2-D matrix?
Pretty simple. We are considering N and B for calculating the optimal solution. Hence, we create a 2-D matrix of size N*B but as B will start from 0, we will need a matrix of size N*(B+1). For a given N and given B, we store the optimal solution for the given N and B in table[N][B].
Assumptions:
1. price[N] : Array containing price of each toffee.
2. calorie[N] : Array containing calorie content for each toffee.
3. table[N][B+1] : Table to store optimal solution for all the sub-problems.
Algorithm:
STEP 1: For each toffee and each budget do (toffee = 0 to N-1 & budget = 0 to B):
If the current budget is less than price of the current toffee we don't buy the current toffee and hence maximum calorie we get will be one of the following:
1. If we only have one toffee i.e. current toffee:
Maximum calories will be 0 as we are left with no other toffees.
2. Else:
Maximum calories will be that of without buying the current toffee i.e. matrix[toffee-1][budget].
If current budget is greater than or equal to the price of the current toffee, the maximum calorie we can obtain will be one of the following:
1. If we only have one toffee i.e. current toffee, we buy the current toffee:
Maximum calories will be that of current toffee as we don't have any other toffees to consider.
2. Else:
Maximum calories will be maximum calories obtained by either buying the current toffee or not buying the current toffee. i.e. Max(table[toffee-1][budget], calorie[toffee] + table[toffee-1][budget - price[toffee]]).
STEP 2: print table[N-1][B]
As we are calculating solution for all the sub-problems and storing them in a matrix, the time and space complexity for the above algorithm is O(N*B).
Link to view/download code for the given problem: https://goo.gl/n7AZu3
NOTE:
Now if you notice carefully, this problem is very similar to standard 0-1 Knapsack problem that we encountered earlier in Dynamic Programming. If you're not familiar with the standard 0-1 knapsack problem, I'll highly recommend to read about it here: https://goo.gl/qck9o3
So, if you are able to identify and reduce the given problem into some standard problem, you can solve the given problem in a very similar way for solving that standard problem. Also, it saves a bunch of time if you have a good grasp of common standard problems.
Hope you liked the tutorial, for any suggestions or improvements, please comment in the comment section below. Thank you for reading.
Comments
Post a Comment