1. We are given n objects and a knapsack. Each object I has a positive weight w, and a positive weight w, and a positive profit p. The knapsack can carry a weight not exceeding m.
2. Our aim is to fill the knapsack in such a way so that the sum of weights of included objects is not greater than m and the sum of profits of all included objects is maximum.
3. Mathematically this problem can be given as:

$$\text{Maximize} \sum_{i=1}^n Pi Xi \\ Subject \ \ to \ \ \sum_{i=1}^n Wi Xi \lt = m \\ x_i = 0 \ \ or \ \ 1, 1\lt = i\lt=n$$

1. It is clearly understood that the knapsack problem is a maximization problem of cost. However, this is not a very big problem since this difficulty is easily overcome by replacing the objective function- $∑_{i=1}^n PiXi$, since, $∑_{i=1}^n PiXi$ is maximized if -$∑_{i=1}^n PiXi$ is minimized. This modified knapsack problem is stated as,

$$\text{Maximize} \sum_{i=1}^n Pi Xi \\ Subject \ \ to \ \ \sum_{i=1}^n Wi Xi \lt = m \\ x_i = 0 \ \ or \ \ 1, 1\lt = i\lt=n$$

1. In order to solve the knapsack problem we need to conceive the state space tree for the same. Consider a case where n=4 for a given knapsack instance. Assuming a fixed size tuple, the state space tree would be:
2. As per this, SST x_i= 1 if object I is included and 0 if not included. The leaf nodes will be solution nodes. That solution nodes will be answer nodes which corresponds to minimum profit. Take example of leaf node 18 which corresponds to tuple (1, 1, 0, 1) which means we have selected object number 1, 2 and 4 but not object number 3. Similarly node 16 would correspond to (1, 1, 1, 1) and 31 to (0, 0, 0, 0).
3. Instead of using a blind FIFO-BB, we may use LC search. According to LC search for every node x of the SST let c(x) be the cost of the node x. Let c’(x) be an estimated of c(x) and u(x) be an upper bound on this cost. Hence, the following relationship should always be true c’(x) <= c(x) <=u(x).
4. The selection of c’(x) and u(x) in knapsack problem is not simple and straightforward. Hence, consider the following example to understand how c’(x) and u(x) are calculated and then how SST is developed.
5. Consider the knapsack instance n=4, (p_1,p_(2,),p_3, p_4)=(10,10,12,18), (w_1,w_2, w_3,w_4)=(2,4,6,9), and m=15. Let us trace the working of an LC branch and bound search using c’ () and u (). The search begins with the root as the E-node. For this node 1, we have c’ (1) = -38 and u (1) =-32.
6. The computation of u (1) and c’ (1) is done as follows. To find u (1) we can through the objects from left to right starting from object 1 and add these objects into the knapsack until the first object that doesn’t fit in encountered. At this time, the negation of the total profit of all the objects in the knapsack is assigned to u (1). For example in this case, we insert objects 1, 2, 3 without weights 2, 4, 6. The combined weight is 32. The weight of the fourth object is 9 which is added exceeds m=15. Now the negation of profit of added objects is – (10+10+12) which is assigned to u (1).
7. Although we cannot add the fourth object entirely, we can still add a fraction 3/9 of it. In that case, the profit will be – (10+10+12+ (3/9)*18) =-38. This will be the value of c’ (1).
8. Now node 1 is the E-node which is expanded and its two children, nodes 2 and 3 generated. Now node 2 corresponds to a situation where 1 objects is already selected and now we try to fill the knapsack with each remaining objects. The logic stated earlier for calculation of c’ (1) and u (1) will remain exactly same for c’ (2) and u (2) and hence we see the same value of c’() and u() for node 2 also.
9. However node 3 corresponds to a situation where object 1 is not selected and now we try to fill the knapsack with each remaining object. Moving in sequence we now we fill the knapsack with object 2 and 3 but not 4 since we would exceed the knapsack capacity. This gives us u (3) =10. Although we cannot add the fourth object directly, we can still add a fraction 5/9 of it. In that case, the profit will be – (10+12+ (5/9)*18) =-32. This will be the value of c’ (2).
10. It should now be understood that the left child of a given node x will always have the same value of c’ () and u (as node x. Now c’ (2) <=c’ (3). Hence, node 2 is the next E-node. It is expanded and node 4 and 5 is generated. Both nodes get added to the list of live nodes. Node 4 is the live node with least c’ value and becomes the next E-node. Node 6 and 7 are generated and added to the list of live nodes. The next E-node will be one of nodes 6 and 7. Let us assume it is node 7. Its two children are nodes 8 and 9. Node 8 is an answer node.
11. The path from root node to answer node is 1, 2, 4, 7, 8. From this path one cannot figure out which objects are exactly selected. Hence we may associate with each node a one bit field called tag. The sequence of tag bits from the root node to answer node will give us the xi values. Thus, we have tag(2)=tag(4)=tag(6)=tag(8)=1 and tag(3)= tag(5)=tag(7)=tag(9)=0. The tag sequence for the path 1, 2, 4, 7, 8 is 1 1 0 1 and so xi=1 x2=1 x3=0 x4=1.