GREEDY ALGORITHMS- Proof Technique: Greedy Stays Ahead A shipping company transp
ID: 3827119 • Letter: G
Question
GREEDY ALGORITHMS-
Proof Technique: Greedy Stays Ahead
A shipping company transports packages from Los Angeles to San Francisco every day. Their volume is large enough that the company may need to send multiple trucks every day. Each truck has a limited amount of weight W that it can carry. Packages arrive at the LA station one by one, each package i having a weight wi. Since the station is small, only one truck can be at the station at any time. The company’s policy is that packages must be sent out in the order received. Their current greedy policy is to load the packages into the truck in the order received; whenever a package does not fit, the truck is sent out and the package is held for the next shipment. Prove that for a given set of packages, with their corresponding weights, the company’s current strategy minimizes the number of trucks that are needed.
Explanation / Answer
The Greedy approch suggested here minimizes the number of trucks needed and gives the optimal solution.
Proof by contradiction: Assume that the approach doesnot yield minimum number of trucks required. Suppose the approach yields 'M' and the actual solution is 'm' with m<M. Then this means we can deliver all packages with lesser number of trucks. However, we are loading the truck till maximum number of packages (loaded into the truck to be sent in the order in which they arrived) get fit into the truck. Using lesser trucks than M would mean loading the trucks with more packages than the ones that could fit in by the greedy strategy. This is not possible since this would either lead to: (a) Over-flowing the truck's capacity or (b) Violating the order in which the packages need to be sent. This leads to a contradiction that m<M. Also, loading the trucks with lesser number of packages than the ones found with the greedy strategy would lead to increasing the number of trucks, causing heavy underflow in all trucks.
Thus, the greedy-strategy tries to utilize each truck's capacity to as much extent as possible, minimizing underflow. Hence, this approach yields the minimum number of trucks that are needed.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.