Problem LinkDifficultyChallenge PrerequisitesDijkstra, knapsack problem, creativity ProblemThere is an undirected weighted graph and a set of orders. Each order is described with the node where it should be taken, the node where it should be delivered, its' weight and the profit that the delivery boy will get upon its' delivery. Given the stregth of the delivery boy, the maximal distance he can walk in total, the road system and the set of orders. Try to find the way to get the maximal possible profit. ExplanationConsider a graph with 2 nodes and one edge between these nodes of the length of 1. Let the delivery boy stand at the node numbered the 1^{st}, the distance he can walk be equal to 1. Moreover, all the orders have the pickup node equal to 1 and the destination node equal to 2. This partial case of the problem is nothing but a knapsack problem which is indeed NPcomplete, so there is no efficient precise solution. During the contest, especially, the first few days there were only a few submissions to this problem with a nonzero score. Let's discuss a few simpletocode approaches, that can be the starting points for more serious solutions and their possible improvements. Idea #1: a random walkLet's generate a random path in the given graph with the length not exceeding the provided constraint D. Of course, the more the length of the path is, the better. So there is no sense in stopping the generation of this path, unless all the edges outgoing from the current path's endpoint have greater lengths than the remaining allowed distance. Now we have a random path. For each node of this path, let's calculate its' last position of occurrence. Now we can iterate through the nodes of this path in order they appear and, if there is an order in the current node and the destination node will occur later (we can check it with the precomputed last occurrences' positions) and the current carried weight plus the weight of this order doesn't exceed the maximal weight the delivery boy can carry, we should take this order. Similarly, if we're carrying some orders that should be delived to the current node, we can leave them now. What can be improved
Idea #2: greedy choiceLet's calculate the shortest distance from the source node S to all other nodes. It can be done using Dijkstra's algorithm. Now, let's pick the most profitable order such that 2(distance from S to A + distance from S to B) doesn't exceed the remaining distance we can walk. Here A is the pickup node for the order and B is the destination node. Then, we can deliver this order by going from S to A by the shortest path, picking the parcel, then, getting back to S, then going to B and leaving the parcel, and, finally, going to S. If, at some moment, we can't find any order, satisfying the constraint above, then we can just finish the program. What can be improved
Setter's SolutionCan be found here Tester's SolutionCan be found here
This question is marked "community wiki".
asked 06 Oct '15, 06:38
