Consider the following Trick-or-Treat problem. You live on a street with n houses. You have a...

 

Transcribed Image Text:

Consider the following Trick-or-Treat problem. You live on a street with n houses. You have a bag to carry your Halloween candy, but your bag can carry at most K ounces of candy. You are given for each house i, an integer weight w; (in ounces) of the candy that the people in house i are handing out. Each house gives out one piece of candy. You can visit each house at most once. Your problem is to collect the largest number of pieces of candy from the n houses without exceeding the capacity of your bag. Now consider the following greedy algorithm. Sort the houses according to the weight of the candy they are providing. Collect candy from the houses starting from the house that provides the lightest candy, then the next lightest, ... until your bag is full. a. State and prove a "swapping lemma" for this greedy algorithm. b. Write a proof that uses your swapping lemma to show that the greedy algorithm does indeed collect the largest number of pieces of candy without exceeding the weight of your bag. Note: You must show that it is not possible to collect more pieces of candy than the greedy algorithm. Do not appeal to any general principles. You must incorporate your swapping lemma as you stated. Consider the following Trick-or-Treat problem. You live on a street with n houses. You have a bag to carry your Halloween candy, but your bag can carry at most K ounces of candy. You are given for each house i, an integer weight w; (in ounces) of the candy that the people in house i are handing out. Each house gives out one piece of candy. You can visit each house at most once. Your problem is to collect the largest number of pieces of candy from the n houses without exceeding the capacity of your bag. Now consider the following greedy algorithm. Sort the houses according to the weight of the candy they are providing. Collect candy from the houses starting from the house that provides the lightest candy, then the next lightest, ... until your bag is full. a. State and prove a "swapping lemma" for this greedy algorithm. b. Write a proof that uses your swapping lemma to show that the greedy algorithm does indeed collect the largest number of pieces of candy without exceeding the weight of your bag. Note: You must show that it is not possible to collect more pieces of candy than the greedy algorithm. Do not appeal to any general principles. You must incorporate your swapping lemma as you stated.