Assume that you are an employee in a Pizza Bakery and are given a list of ingredients that can be used in a pizza along with a list of their costs and sell prices. The index of an ingredient in the ingredient list is the same as its cost index in the costs list and its price index in the price list. The inputs look like this: Ingredients = {Cheese, Tomato, Basil, Green Pepper, Salami, Ham, Bacon, Olive} Costs = {2 , 1 , 1 , 1.5 , 3 , 4 , 8, 1} Price = {3 , 2 , 0, 0.5 , 1 , 7 , 7 , 1.5} We can say that Cheese costs $2 and if a pizza contains cheese we charge an additional 3$. Unfortunately, your manager is kind of an annoying person and puts a rule which as follows: If a customer asks for ingredient index x and ingredient index y where x < y, the customer must add the other ingredients between index x and y. For example, if a customer asks for Basil and Ham, the customer must also buy Green Pepper and Salami. The manager tells you to write a program that finds the sequence of ingredients that has the maximum revenue for the bakery. (You do not need to write the program) Demonstrate five steps of Dynamic programming for such a program. Give asymptotic complexity of the program.
Assume that you are an employee in a Pizza Bakery and are given a list of ingredients that can be used in a pizza along with a list of their costs and sell prices. The index of an ingredient in the ingredient list is the same as its cost index in the costs list and its price index in the price list. The inputs look like this:
Ingredients = {Cheese, Tomato, Basil, Green Pepper, Salami, Ham, Bacon, Olive}
Costs = {2 , 1 , 1 , 1.5 , 3 , 4 , 8, 1}
Price = {3 , 2 , 0, 0.5 , 1 , 7 , 7 , 1.5}
We can say that Cheese costs $2 and if a pizza contains cheese we charge an additional 3$.
Unfortunately, your manager is kind of an annoying person and puts a rule which as follows:
If a customer asks for ingredient index x and ingredient index y where x < y, the customer must add the other ingredients between index x and y.
For example, if a customer asks for Basil and Ham, the customer must also buy Green Pepper and Salami.
The manager tells you to write a program that finds the sequence of ingredients that has the maximum revenue for the bakery. (You do not need to write the program)
Demonstrate five steps of Dynamic programming for such a program.
Give asymptotic complexity of the program.
Step by step
Solved in 3 steps with 3 images
