CSC373: Greedy Algorithms Daniel Zingaro
daniel.zingaro@utoronto.ca
1 Item Purchases
You have to buy n items, 1 item per month for n months. Each item starts out costing $100, but then, each month, item j increases in cost by rj > 1. (So, after m months, item j costs 100 ∗ rjm.) In what order should you buy the items so that your total cost is as small as possible?
• Suppose that r1 = 2, r2 = 4, r3 = 3. What is the smallest possible cost for purchasing the items, and what is the order of purchasing that gives you this minimum?
• Here is a proposed greedy algorithm for solving the problem in general: purchase the items in sorted order starting with the smallest r value. Argue that this algorithm is not correct.
• How about this one instead: purchase the items in sorted order starting with the largest r value. Using further examples, can you convince yourself whether this algorithm is correct?
2 Item Sales
You have to sell n items, 1 item per month for n months. Each item starts out selling for $100, but then, each month, item j decreases in value by 0 < rj < 1. (So, after m months, item j sells for 100 ∗ rjm.) In what order should you sell the items so that your total profit is as large as possible?
• Suppose that r1 = 0.5, r2 = 0.4, r3 = 0.3. What is the largest possible profit for selling the items, and what is the order of selling that gives you this maximum?
• Suppose that r1 = 0.75, r2 = 0.5, r3 = 0.01. What is the largest possible profit for selling the items, and what is the order of selling that gives you this maximum?
• Do you think that there’s a correct greedy algorithm that sells in increasing order? Decreasing order?