This question is from job interview for a software company.
"You are given an undirected connected weighted graph with $n$ nodes. The weight function represents transportation costs. In each node there are some items with given volume and price. There are totally $M$ items. You have a knapsack with volume $W$ and your goal is to traverse from node $A$ to node $B$ collecting some of the items and maximizing your profit. You can take a given item only once."
Check this example with $W=16$:
You can take $(6,3)$ from $A$ and $(10,8)$ from $B$ making profit $3+8-2=9$.
Another choice is $(6,3), (3,5)$ from $A$ and $(5,5)$ from $B$ with profit $11$.
You can also take $(3,5), (8,4)$ from $A$ and $(5,5)$ from $B$ with profit $12$.
However the best decsion is to take $(6,3)$ from $A$, $(4,7)$ from $C$, $(6,20)$ from $D$, then go back to $A$ and go to $B$.
Another best route is $(3,5)$ from $A$, $(6,20)$ from $D$ and $(5,5)$ from $B$.
They both need $6$ for transportation costs, so the total profit is $24$.
I had 15 minutes to suggest an algorithm with running time $O(|E|.M.S_M)$ where $S_M$ is the total volume of all items... needless to say I failed...