I've got a bit stuck trying to solve the following problem:
A number of transport companies each offer various means of transportation, for example company A offers:
Cost Distance
Bus $1 10km
Train $2 15km
Plane $5 20km
Given that it is permitted to choose only one means of transport per company, find the minimum cost given that you must travel x km. You maybe assume that for any particular company a method of transportation will be cheaper than another method if it travels less distance. So in the above example, a bus could not be more expensive than a plane as 10km < 20km.
Can any one suggest an approach to this problem? Perhaps there's a well known algorithm that's applicable? I'm pretty sure it can't be solved in polynomial time (even any insight here would be appreciated!).
Thanks!
This looks like the knapsack problem, which is $\operatorname{NP}$-complete. You can easily verify the problems are similar if you consider a related problem where each company offers only one mode of transportation. Then you would have:
$$\left[\begin{matrix} C_1\\C_2\\...\\C_i\end{matrix}\right] = \left[\begin{matrix}(s_1, d_1)\\(s_2, d_2)\\...\\(s_i, d_i)\end{matrix}\right]$$
Where $C_i$ denotes company $i$, $s_i$ denotes the sale price of transportation for company $i$, and $d_i$ denotes the distance you can travel using company $i$.
Now consider if you were trying to travel $j$ total miles for the cheapest price. This is precisely the same as the knapsack problem, with no (known) polynomial-time algorithm.