Does anyone know of a polynomial time algorithm for solving the multiple knapsack problem? I'm not really looking for lengthy code, just the general idea of how this problem can be solved in non-exponential time. Thanks.
Printable View
Does anyone know of a polynomial time algorithm for solving the multiple knapsack problem? I'm not really looking for lengthy code, just the general idea of how this problem can be solved in non-exponential time. Thanks.
My "problem" is that of the first few hundred pages i looked through in the google search they either contain abstracts for research papers or other semi-related stuff that isn't of any use.
You might get better results if you explained what the multiple knapsack problem is, not simply assume that everyone is familiar with it, or has the inclination to do research to help you.
The multiple knapsack problem goes something as follows. A thief robbing a safe finds it filled with differnet types of items of varying size and value, but has only a few small knapsacks of varying capacity to use to carry the goods. The multiple knapsack problem is to find the combination of items the thief shoud choose to put in the knapsacks in order to maxamize the total value of all the stolen items.
The regular knapsack problem can easily be solved using dynamic programming (with or without memoization) but the problem space is much too large in the multiple knapsack problem (as far as I know) to use dynamic programming.
This is really one of those things that you'd either know or not know.