# 0/1 Multidimensional knapsack problem.

• 03-07-2012
WhoCares
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,...,n} p(j)x(j)st    sum{j=1,...,n} r(i,j)x(j) <= b(i)       i=1,...,m                     x(j)=0 or 1  ```
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?
• 03-07-2012
oogabooga
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
• 03-07-2012
laserlight
Thread moved to General Discussions. Note that this has been posted elsewhere.