Consider the following instance of the $0 -1$ Knapsack problem:
It is required to find all the optimal solutions to this instance using the branch and bound technique.
max 6X1+11X2+16X3+21X4+26X5
Subject to 4X1+8X2+12X3+16X4+20X5<32
and Xi=0 or 1 for i=1,…,5.
Can anyone please explain the meaning of above 3 lines ?
does it mean ,profit = <6,11,16,21,26> , weight = <4,8,12,16,20> and maximum weight = 32 ?
@Arjun Sir, Can you verify my approach?How to formulate it as search tree? As every variable has 2 possible outcomes (0 or 1),$\therefore$ Solution space is $2^{5} = 32$. Feasible solution is the set of all possible values that satisfy the problem's constraints. Constraints says that maximum weight of Knapsack < 32 and $X_{i}=1, \forall i\in{1\cdots5}$ is weight of items. Max is calculated whenever $X_{i}=1, \forall i\in{1\cdots5}$ and multiplying with the profit of corresponding items to be placed in Knapsack. It is required to find maximum among all the feasible solution. For example : 1 possible Feasible solution is (0,0,0,0,0). $Max :6*0+11*0+16*0+21*0+26*0 = 0.$ Following are the other feasible solution. \begin{array}{|c|c|c|c|c|c|} \hline X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & Max\\ \hline 1 & 1 & 1 & 0 & 0 & (6+11+16)= 34 \\ 1 & 0 & 0 & 1 & 0 & (6+21)= 27 \\ 1 & 1 & 0 & 1& 0 & (6+11+21)= 38 \\ 0 & 1 & 0 & 0 & 1 & (26+11)= 37 \\ 1 & 0 & 0 & 0 & 1 & (6+26)= 32\\ 0 & 1 & 1 & 0 & 0 & (11+16)= 27\\ 0 & 1 & 0 & 1 & 0 & (11+21)= 32\\ 1 & 0 & 1 & 0 & 0 & (6+16)= 22\\ \hline \end{array}
Further Read: https://cs.stackexchange.com/q/1052
64.3k questions
77.9k answers
244k comments
80.0k users