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?
