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 ouse gives out one piece of candy. You can visit each house at most once. Your problem is to collect the argest 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 re providing. Collect candy from the houses starting from the house that provides the lightest candy, then he 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. Use the following steps to prove Euclid's Lemma: Let P be a prime and let a,b E N. If Pab, then P \ a or P\b Let TnEN: P nb, show that a TandP ET, and conclude that T must have a least element c by the WOP. Use the division algorithm to show that cn for every n T Use this fact to show that c=1, and conclude that P | b