4 ms·
This is, of course, just The Knapsack Problem: http://en.wikipedia.org/wiki/Knapsack_problem http://en.wikipedia.org/wiki/Knapsack_problem It's proven to be NP
by bigiain 12y ago
This is, of course, just The Knapsack Problem: http://en.wikipedia.org/wiki/Knapsack_problem http://en.wikipedia.org/wiki/Knapsack_problem
It's proven to be NP-Hard, but with a well known "good enough" approximation ("the knapsack problem has a fully polynomial time approximation scheme (FPTAS)")
- ojbyrne 12y agoActually that's not quite correct. The knapsack problem has 2 constraints: weight and (traditionally) "utility." This problem has 3 constraints - weight, volume and utility. That probably makes the problem more tractable.
- deleted 12y ago[deleted]
- millstone 12y agoIt's not the knapsack problem. The task is similar: maximize (some relation between) the carried volume and weight. But instead of a finite collection of different items, you have an essentially infinite set of a few items. Also, the weight and volume of each individual item is negligible, so you don't have to worry about the integer nature of the problem, i.e. it's sufficient to give a fractional answer and round down. (That's what makes the knapsack hard - the fact that you can't add fractional items.) This seems like a straightforward linear programming problem, solvable via the simplex method.
- MrBuddyCasino 12y agoYeah linear programming was my first thought, too. How is that "one of the best kept secrets in the air cargo industry"?
- raverbashing 12y ago> How is that "one of the best kept secrets in the air cargo industry"? I guess it's only part of the problem, solving for one plane. In practice you would want to solve for varying demand, for multiple customers, for planes that eventually are delayed, crews that get sick/delayed, for different planes, for routes that pick/drop different cargo at different places. And of course, you want to price all of that in a way that makes you money.
- rs232 12y agoIt is not a secret. It is a basic day to day task to optimize this. If you didn't you'd be out of business very quikcly.
- Dylan16807 12y agoIn addition to the other comments, keep in mind that this is such an enormous knapsack that dumping in items at random is just as efficient as any other method.