Question

3. [10 marks] Suppose we would like to buy n items from SuperCheapStore (SCS); all items are currently priced at 1 CAD. Unfortunately there is no delivery and we have to deliver them home. The bad news are: we can fit only 1 item in our truck: it takes one day to drive home and back. There is even worse news -SCS charges us for the storage of undelivered items and the charge for storage of te i growth exponentially as original price times factor c 1 each day. It means that if item i is picked up d days from now, the charge will be 1 CAD In which order should we pick up our items from SCS so that total amount of charges is as small as possible. Develop a greedy algorithm to solve this problem assuming that Gメc, for iメJ. Prove that your algorithm gives an optimal solution. What is the running time of your algorithm?

Answer 1

Algorithm:

Step 1: For all items bought , sort them in the decreasing order of their cj . i.e ( if cj of an item is maximum , it will be at first, if is least it will be last.).

Step 2: Load the items in truck in the same sorted order i.e if an item has highest cj, it will be loaded on first day, if it has least it will be loaded on last day.

Step 3: For each item in the bought list, follow the step 2, and calculate extra charge to be paid for all un delivered item.

Optimal Solution:

                               If we load the item in truck in any random order of cj, the sum of extra charge calculated for each item won’t be as small as possible as the item with highest cj may be picked at last which leads to automatic sum of extra charge for all items to be more than by the algorithm described above. For any other way of loading the items bought into the truck, the sum of extra charges will be more than calculated from above algorithm. Thus above solution is optimal.

Running time: If n is the number of items bought.

=O(sorting the items as described in the algorithm)

=O(nlogn)