Thread: Multiple Knapsack Problem

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    3

    Multiple Knapsack Problem

    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.

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    3
    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.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    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.

  4. #4
    Registered User
    Join Date
    Nov 2001
    Posts
    3
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. knapsack problem
    By fnfn in forum C++ Programming
    Replies: 1
    Last Post: 07-19-2007, 03:14 PM
  3. problem while opening files from multiple directories
    By V.G in forum Windows Programming
    Replies: 2
    Last Post: 11-08-2004, 03:29 PM
  4. small reference problem
    By DavidP in forum C++ Programming
    Replies: 6
    Last Post: 06-21-2004, 07:29 PM
  5. Replies: 5
    Last Post: 12-03-2003, 05:47 PM