|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``grid''
by PARASHAR on 2008-06-26 05:31:07 |
|
| You have a list of items you need to buy today, and you know the locations (represented as points on a cartesian grid) of a few stores in the area. You also know which of these stores are selling each item on your list, and at what price each store sells it. Given the price of gas, what is the minimum amount you need to spend in order to buy all the items on your shopping list and then drive back home? You start and end the journey at your house, which is located at (0,0).
To make matters interesting, some of the items on your list may be perishable. Whenever you make a purchase that includes one or more perishable items, you cannot drive to another store without first stopping back at your house. Every item on your shopping list is guaranteed to be sold by at least one store, so the trip will always be possible.
|
| | [ reply | up ] |
|
|
|
|
|
|
