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$:enter image description here

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

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

Under your desired complexity, this problem is NP-hard, so either there are some additional restrictions, or your interviewer is evil.

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.

The other direction of the proof is trivial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.