(3) A student is planning to do some jobs to earn some money. She must supply her own equipment. Job Payment for doing the job Equipment required Wash Windows $30 rags, bucket, ladder Pick Apples $40 bucket, ladder $35 ladder, saw Prune Trees ------------- Equipment Cost $5 $10 Rags Bucket Ladder Saw $50 $45 (a) Formulate the problem of determining which jobs to do and which equipment to buy to maximize her profit as a max weight closed set problem. Your answer should include an explicit directed graph with weights on the vertices. Do not solve, however, do explain how a max closed set would be used to answer the question. (b) Formulate the specific max weight closed set problem of (a) as a max-flow min-cut problem. Your answer should include an explicit network with vertices s and t, and capacities on the arcs. Explain how to use the output from the max flow algorithm would be used to get a max weight closed set. (c) Give the max flow and min cut for your problem in (b). You don't have to show the steps you took to get to the max flow. (d) Use your min cut in (c) to find the max weight closed set for your problem in (a). Then tell the student which equipment she should buy and which jobs she should do to profit, and what her profit will be. maximize her (3) A student is planning to do some jobs to earn some money. She must supply her own equipment. Job Payment for doing the job Equipment required Wash Windows $30 rags, bucket, ladder Pick Apples $40 bucket, ladder $35 ladder, saw Prune Trees ------------- Equipment Cost $5 $10 Rags Bucket Ladder Saw $50 $45 (a) Formulate the problem of determining which jobs to do and which equipment to buy to maximize her profit as a max weight closed set problem. Your answer should include an explicit directed graph with weights on the vertices. Do not solve, however, do explain how a max closed set would be used to answer the question. (b) Formulate the specific max weight closed set problem of (a) as a max-flow min-cut problem. Your answer should include an explicit network with vertices s and t, and capacities on the arcs. Explain how to use the output from the max flow algorithm would be used to get a max weight closed set. (c) Give the max flow and min cut for your problem in (b). You don't have to show the steps you took to get to the max flow. (d) Use your min cut in (c) to find the max weight closed set for your problem in (a). Then tell the student which equipment she should buy and which jobs she should do to profit, and what her profit will be. maximize her