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 companys 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 companys current strategy minimizes the number of trucks that are needed.