@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}
Optimal Solution is (1,1,0,1,0), for which we are getting Max = 38.
Some Infeasible solution
$\begin{array}{|c|c|c|c|c|c|}
\hline
X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & Infeasible Weights\\
\hline
0 & 0 & 0 & 1 & 1 & 16+20>32 \\
0 & 0 & 1 & 0 & 1 & 12+20=32 \\
1 & 1 & 0 & 0& 1 & 4+8+20=32 \\
0 & 1 & 1 & 1 & 0 & 8+12+16>32 \\
\hline
\end{array}$
Max possible nodes in search tree will be 9, as these are feasible solution and remaining 32-9=23 are infeasible solution.
Further Read: https://cs.stackexchange.com/q/1052
