Link to the problem on UVa Online Judge
Link to the pdf version
In this problem we want to create a binary decision tree which sum of all of the searches is minimum.
Let's understand the problem with an example:
Let's think we have an array like shown in the picture : [1, 2, 3, 7, 8, 9, 10, 20, 21]
For the first apple to eat we have several options, let's assume we choose 7 to eat first, no matter which apple is sweet at the end, how many times 7 must be eaten? 9 times, because if 1, 2 or 3 is sweet first we have chosen to eat 7, then we know the sweet is on the left side of 7 and we go to the left subtree, if 7 is sweet we have already eaten it, if 8, 9, 10, 20 or 21 is sweet, first we eat 7 and then we move to the right subtree.
So if we choose 7 to be eaten at first, the total cost would be something like this : 7*9 + cost(left_subtree) + cost(right_subtree)
If we use indexes for the cost function it would be something like this: 7*9 + cost(0, 2) + cost(4, 8)
What if we choose to eat 8 at first? Then the cost would be 8*9 + cost(0, 3) + cost(5, 8), because still 8 must be eaten 9 times no matter which apple is sweet and then recursively solve (0, 3) and (5, 8).
int cost(int i, int j) must calculate the cost of the best decision tree for the numbers in [i...j]
So in order to calculate cost(i, j) we iterate over all possible options for the first apple to be eaten and take the minimum of them as the answer.
What are the basic steps? What if only one apple is remained? We must have already figured it out if only one apple is remained, then cost would be zero.
Formally if i == j then cost is equal to zero.
What if only two numbers are remained? We can eat the lighter apple and figure out if the lighter is sweet or the heavier, then must return weight[i] * 2.
Since there are a lot of overlapping subproblems we memoize answer to each cost(i, j) and use a top-down dynamic programming approach.
Link to the pdf version
In this problem we want to create a binary decision tree which sum of all of the searches is minimum.
Let's understand the problem with an example:
For the first apple to eat we have several options, let's assume we choose 7 to eat first, no matter which apple is sweet at the end, how many times 7 must be eaten? 9 times, because if 1, 2 or 3 is sweet first we have chosen to eat 7, then we know the sweet is on the left side of 7 and we go to the left subtree, if 7 is sweet we have already eaten it, if 8, 9, 10, 20 or 21 is sweet, first we eat 7 and then we move to the right subtree.
So if we choose 7 to be eaten at first, the total cost would be something like this : 7*9 + cost(left_subtree) + cost(right_subtree)
If we use indexes for the cost function it would be something like this: 7*9 + cost(0, 2) + cost(4, 8)
What if we choose to eat 8 at first? Then the cost would be 8*9 + cost(0, 3) + cost(5, 8), because still 8 must be eaten 9 times no matter which apple is sweet and then recursively solve (0, 3) and (5, 8).
int cost(int i, int j) must calculate the cost of the best decision tree for the numbers in [i...j]
So in order to calculate cost(i, j) we iterate over all possible options for the first apple to be eaten and take the minimum of them as the answer.
What are the basic steps? What if only one apple is remained? We must have already figured it out if only one apple is remained, then cost would be zero.
Formally if i == j then cost is equal to zero.
What if only two numbers are remained? We can eat the lighter apple and figure out if the lighter is sweet or the heavier, then must return weight[i] * 2.
Since there are a lot of overlapping subproblems we memoize answer to each cost(i, j) and use a top-down dynamic programming approach.
No comments:
Post a Comment