Consider the
0/1 Knapsack Problem with knapsack capacity m=15. The four items having weights
as (w 1 ,w 2 ,w 3 ,w 4 )=(2,4,6,9) and
profits (p 1 ,p 2 ,p 3 ,p 4 )=(10,10,12,18).
The lower bound c and upper bound u of an intermediate node in
one of the step solving the 0/1 Knapsack Problem using LC Branch and Bound are
-38 and -38 respectively. The lower bound c and upper bound u of next level of nodes in
State Space Tree are

Question

Consider the
0/1 Knapsack Problem with knapsack capacity m=15. The four items having weights
as (w 1 ,w 2 ,w 3 ,w 4 )=(2,4,6,9) and
profits (p 1 ,p 2 ,p 3 ,p 4 )=(10,10,12,18).
The lower bound  c and upper bound u of an intermediate node in
one of the step solving the 0/1 Knapsack Problem using LC Branch and Bound are
-38 and -38 respectively. The lower bound  c and upper bound u of next level of nodes in
State Space Tree are

Answer

First
Node (c,u)=(-36,-36) and
Second Node (c,u)=(-18,-18)

Answer

First
Node (c,u)=(-24,-30) and
Second Node (c,u)=(-32,-32)

Answer

First Node (c,u)=(-38,-38) and Second Node (c,u)=(-20,-20)

Answer

First
Node (c,u)=(-28,-28) and
Second Node (c,u)=(-22,-22)

Crowdly

Consider the 0/1 Knapsack Problem with knapsack capacity m=15. The four items ha...

Want instant access to all verified answers on moodle.spit.ac.in?