0/1 Multidimensional knapsack problem.

This is a discussion on 0/1 Multidimensional knapsack problem. within the General Discussions forums, part of the Community Boards category; Hey ppl. I wont ask any part of code. I just wanna ask ppl who are interested in dynamic programming ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    1

    0/1 Multidimensional knapsack problem.

    Hey ppl. I wont ask any part of code. I just wanna ask ppl who are interested in dynamic programming or artificial intelligence. I'm trying to implement a 0/1 MKP by using tabu search algorithm. The 01MKP uses these two equations.


    PHP Code:
    Max  sum{j=1,...,np(j)x(j)
    st    sum{j=1,...,nr(i,j)x(j) <= b(i)       i=1,...,m                     
    x
    (j)=or 
    The goal is to determine a set of items with maximum profit, which does not exceed the resource capacities.

    Anyway, I just wanna ask ppl who already aware of this problem.

    Here is a data-set to test it.



    PHP Code:
    2 28 // 2 knapsacks, 28 objects 
    1898 440 22507 270 14148 3100 4650 30800 615 4975 
    1160 4225 510 11880 479 440 490 330 110 560 
    24355 2885 11748 4550 750 3720 1950 10500 
    // 28 weights 
    600 600 // 2 knapsack capacities 
    45 0 85 150 65 95 30 0 170 0 
    40 25 20 0 0 25 0 0 25 0 
    165 0 85 0 0 0 0 100 
    // #1 constr. 
    30 20 125 5 80 25 35 73 12 15 
    15 40 5 10 10 12 10 9 0 20 
     60 40 50 36 49 40 19 150 
    // #2 constr. 
    Lets talk about item #1 and knapsack #1.
    the weight of item #1 is 1898. the capacity of knapsack #1 is 600. (smaller than item). and in the constr. #1 list, the constraint of item #1 for knapsack #1 is 45.

    Can someone tell me where is 45 comes from?
    Last edited by WhoCares; 03-07-2012 at 01:52 PM.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I think you're interpreting the data incorrectly.
    First and foremost, there's only ONE knapsack!
    I believe the numbers mean:

    2 constraint dimensions
    28 objects
    List of values for 28 objects
    600 1st dimension max
    600 2nd dimension max
    First dimension constraint list for 28 objects
    Second dimension constraint list for 28 objects
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,772
    Thread moved to General Discussions. Note that this has been posted elsewhere.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Knapsack problem
    By viblic in forum C Programming
    Replies: 8
    Last Post: 12-04-2011, 01:58 PM
  2. 0-1 knapsack problem
    By madennn in forum C Programming
    Replies: 2
    Last Post: 03-29-2011, 07:08 AM
  3. knapsack problem?
    By nimitzhunter in forum General Discussions
    Replies: 7
    Last Post: 01-28-2011, 12:16 PM
  4. knapsack problem ?
    By nmt1402 in forum C Programming
    Replies: 1
    Last Post: 01-26-2011, 06:33 PM
  5. Knapsack Problem
    By Fork in forum C Programming
    Replies: 4
    Last Post: 11-13-2006, 11:42 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21