The Acme Baking Company (ABC) produces custom cakes.

Each cake takes exactly one day to create.

Only one cake may be baked each day.

Each cake provides a profit to ABC.

Each cake must be delivered at the end of a specified day.

The cake may be baked on, or at any time prior to, the delivery day

For a ten-day period, ABC has the following order list:

Order #	Delivery Day	Profit
1	4	70
2	4	20
3	6	20
4	4	40
5	10	70
6	2	10
7	8	80
8	2	20
9	3	70
10	9	80
11	4	60
12	3	70
13	4	80
14	8	60
15	9	40
16	3	50
17	3	20
18	5	100
19	10	90

20

3

90

1. Outline a greedy strategy you can use to schedule the cake production for the next 10 days.

2. What is the schedule produced using this strategy?

3. What is the total profit?

The owner of ABC is shocked to discover that some customers have returned their cakes and demanded their money back. He realizes that the problem arises when cakes are baked too early – specifically if a cake is baked more than one day before its delivery date. (e.g. A cake delivered on day 5 must be baked on day 4 or day 5 to make a profit).

4. What is the new total profit? (Assume that a returned cake costs you 20).

5. What is the new schedule?

7. What is the new total profit?

Answer rating: 100% (QA)

Step 1 First sort the orders according to the profits in descending orders So after this step we will have following table Order 18 19 20 7 10 13 1 5 ... View the full answer