I have the following problem:
Assume a truck collects items from a grid with n*n size starting at location (0, 0)and delivers them to a terminal (n, n). The truck can move right, left or down. There are few specific cells that contain items of different types/weights. Note that an item can be presented more than ones. The truck has a list of items that should collect before reaching the terminal and should visit each and every one of the specific cells exactly once to prepare the list. The truck consumes energy for carrying the item that is equivalent to the weight of the item, e.g., if it carries three items with the weights of w1, w2 and w3, it consumes w1 + w2 + w3 units of energy per move. This means that if the truck takes the items that are closer to the terminal, it will consume less energy. If the truck carries no items, it consumes no energy.
So far I have seen problems related to minimum cost path. However, here it seems that the path not only needs to have the least cost, but also include all the items in the list. Moreover, I was thinking of starting from the terminal since it needs to find the minimum cost from the terminal. Here is also the recurrence relation, that I have came up so far:
f(i,j) = min(f(i-1,j), f(i,j-1), f(i,j+1)) + w(i,j)
Is this relation valid? Or any ideas how to tackle this problem?
Your recurrence is a good start. But you must also consider how, midway through the operation, the truck already has some objects and does not need to collect them again. For example suppose the truck needs an apple, orange and banana. Call these $1,2,3$.
Now suppose the truck is at location $(3,3)$ and already has an apple. It wants to collect an orange and banana and reach the terminal. The remaining cost can be written
$$w_1 + \min \{ f((3,2), \{2,3\}) , f((3,4), \{2,3\}), f((3,2), \{2,3\})\}$$
Where $w_1$ is the cost to move one space carrying an apple and for example $f((3,2), \{2,3\}) $ is the lowest cost to collect an orange and banana starting from square (3,2).
You must also be careful to set the costs to infinity if we end up in a square from which it is impossible to complete the mission.