Dynamic Programming with bitmasking

I am unable to solve the problem http://www.spoj.com/problems/COURIER/ please help me how to solve this problem . I have seen a solution but not able to get the logic. Please help me out :frowning:

2 Likes

The courier guy has to start from a particular node, and for each delivery, he has to start from a node and reach another node. He can choose any arbitrary order to perform the deliveries.

Let each delivery be denoted by src[i] and dest[i]. (Multiple deliveries to the same pair of cities are stored separately). Since the courier guy can take only one package at a time, we can assume that the guy always moves to the dest[i] when he picks an src[i]. This boils down to a slightly modified version of Travelling Salesman Problem. We define the DP state as follows:

fn(mask, prev) = min( fn(set kth bit in mask, k) + dist[dest[prev]][src[k]] + dist[src[k]][dest[k]] ) for every k not in mask

Here mask denotes the set of deliveries that have been completed and prev is the index(from src[]/dest[] arrays) of the last delivery that has been completed. dist[x][y] represents the shortest distance between the nodes x & y. This can be found using Floyd Warshal algorithm.

The answer is found by iterating over all possible starting masks plus the distance from the starting city -

min(fn(1<<i,i) + dist[b][src[i]] + dist[src[i]][dest[i]] for all values of i)

Overall time complexity would be O(n*n*(2^n)) where n is the number of entries in the src[] array.

2 Likes
//