Q:

Transportation mininum cost problem

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!

A:

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.

