Description
You are encouraged to work in groups (but not more than 2 persons in a group).Show all your computation to get full credit. Please put comments in your code. I will deduct points for uncommented codes. You can write the programs in any language you choose, so long as we can run it. If you use code, other than your own, cite the source.
Problem Statement. Consider that you are working for a delivery service, where you can go to the warehouse and pick items to deliver. Each item i has a cost ci and weight ci, as well as the address to where to deliver. You have a limit W on how much weight your van can carry. For every item you deliver, you earn 10% of its cost
You are also provided with a map of the town with all the possible of addresses of the items in the warehouse, and the distances between them. Every mile you travel costs you $1.
For simplicity you can consider the items are packaged and cannot be divided further. Also there is a direct path between all pairs of addresses, although the distances may di er. Each address receives exactly one item.
-
Develop an algorithm, where given the list of items, their weights, costs and delivery ad-dresses, you can select the items to pick for 1trip, that brings you maximum pro t. Clearly explain the algorithm in english (Step1, Step2,..etc) and demonstrate how it works for an example problem (20+20=40)
-
Implement the algorithm and try it on 5 di erent set of inputs. Each input consists of a list of items and a complete graph of addresses, along with their distance. There should be at least 200 items on the list and 200 addresses. Submit your code and your results (20+20=40)
-
Write a short (3 page 11point font report) on how you developed the algorithm, its usefulness, the results, discussion about the advantages and drawbacks of your method. Also discuss whether such algorithms are available publicly, and what future enhancements can be made. Include references as appropriate (20)
1
