Fighting with computers

Computers are not always friendly.

Thursday, June 26, 2008

Shopping list problem


Definitely this has been the most challenging problem I've found on the Code Jam practice site. It asks you to determine the optimal selection of what to buy where. With a couple of twists: the cost of going from one place to another is factored in; plus a rule that forces you to drive back home whenever you're buying perishable goods.

The approach that worked for me was to first consider the different combinations of articles from different shops, just to obtain the list of shops to visit for each instance. Each one of list of shops to visit is a traveling salesman problem (perishable rule just changes the cost of some of the links).

Combine both costs, the article's prices at selected shops and the transportation costs to determine how much each realization will amount. The minimum case is the answer you're looking for.

The main problem I faced with the large set is that unless the code is quite efficient (and mine was not) it will take a long long time to finish the calculation.

0 Comments:

Post a Comment

<< Home