# Knapsack in graph

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...

• Interesting problem. What is the |E| vector? – danielmhanover Jul 15 '15 at 3:56
• |E| is number of edges in the graph, I assume – Edward Doolittle Jul 15 '15 at 5:28
• Yes, |E| is the number if edges. – mr-fotev Jul 15 '15 at 8:25

We can reduce the Hamiltonian path problem to this problem. Suppose we have a hamiltonian path problem with graph $G' = (V', E')$. We reduce it to $G = (V, E)$. $V = V'$. On each node $v \in V$, place an item with weight $1$ and value $2n$. For every edge $e' \in E'$, construct an edge $e \in E$ connecting the same nodes and with cost $1$. There is a hamiltonian path (not cycle) in the graph if and only if there exists a solution for this problem for which the profit is exactly $2n^2 - (n-1)$.
To see this, suppose such a solution exists. Then, clearly all $n$ items must have been picked up, since there exists no other way to get the sum to be this high. It implies that we traversed at most $n-1$ paths. Since we must have visited $n$ nodes and traversed $n-1$ paths, this forms a hamiltonian path in the graph.