Knapsack Problem - Branch and Bound Technique Summary

Welcome to CSE Guru. In this session, we will discuss knapsack problem using branch and bound technique. In the previous session, we have implemented the same knapsack problem using branch and bound technique step by step. But we have not implemented the construction of the state space tree. Now, in this session, for the same example, we will implement the construction of the state space tree step by step. Okay. The problem is, solve the following knapsack problem using branch and bound. technique. Given the following data, here the capacity of knapsack is 10 and here they have given four items with its corresponding weight and value. Actually, we need to find value by weight ratio and then we have to order this value by weight ratio in decreasing order. But already here in the problem itself, they have given this value by weight ratio in decreasing order only. So, no need to do that step. Suppose if they have given item weight and value in the sense Next step, we need to find the value by weight ratio and then we have to order the elements according to the value by weight ratio in decreasing order. That we have to follow. Okay. Since already it is in decreasing order of value by weight ratio, no need to do anything. We will continue the procedure. And here in NAVSAC problem using branch and bound technique, we need to calculate the upper bound value in each step. And the upper bound value we will calculate with the help of the formula uv equal to v plus m minus w into vi plus 1 divided by wi plus 1. v is nothing but the total value of all the items added into the knapsack. And m is the maximum capacity and w is total weights of all the objects placed into the knapsack. And vi plus 1 divided by wi plus 1 this is the value by weight ratio of the next item. Suppose if we are considering first item in the sense in that step we need to consider value by weight ratio of the next item. So this is a formula to calculate the upper bound value. Now with this we will implement the construction of the state space tree. In knapsack problem using branch and bound technique the construction of the state space tree is unique. That is the state space tree will be a binary tree. Okay only two nodes will be there. Left subtree and right subtree. Left subtree represents if you are considering any item to include it into the knapsack bag in the sense that item we will place as a left subtree. Suppose if you are not going to consider the particular item we are excluding that item in the sense that will be added as a right subtree and here the state space tree is a binary tree only. Each node will have at most maximum two children's one. So, initial state space tree is we have to consider this is the 0th level without considering any item that is the initial stage and here w is 0 and v is also 0 and what is the upper bound value? So, upper bound is values this formula we have to implement ok. So, value is 0 plus m minus w, m is the maximum capacity. So, 10 minus w is also 0. into value by weight ratio of the next item that is 0th item we are considering. So value by weight ratio we need to consider the first item okay so it is 10. So here we will get the upper bound value 100. So this is the initial stage and here this will be considered as item 0 okay. Next with this node we will continue to construct the next level components. So next level consider item 1. Already I said if you are including item 1 that will be added as a left subtree. If you are not including item 1 that will be added as a right subtree. Okay. So in both the cases we need to find the upper bound value. So here since we are considering the first item its weight and value we need to include. Weight is 4 and value is 40. Next we need to calculate the upper bound value. So here. M minus W, M value is 10, W is 4 and the remaining capacity is 6. So, meaning is if you are including this item into the NAVSAT, it will not destroy the problem constraint. What is the problem constraint? There are two constraints here. One is whenever you are adding any item into the NAVSAT, it should not exceed the maximum capacity. So, here the maximum capacity is 10 and also it should maximize the profit. At the end since we are calculating the upper bound value at the end obviously we will get the upper bound value only. So profit will be maximized only. So this is M minus W. Then the upper bound is value, value is 40 plus m minus w is 6 into value by weight ratio of the next item. Now we are considering first item, value by weight ratio of the next item is 6. So here the upper bound value we will get it as 76. Okay, suppose if you are not going to consider, so this is with item 1 and this is without item 1. Suppose if you are not going to consider this first item to add it into the knapsack in the sense weight will be 0 and also value will be 0 and m minus w if you are considering in the sense 10 minus 0. So this is 10 only right. So here upper bound value is value is 0 plus m minus w this value is 10 into value by weight ratio of the next item it is 6. So here we will get the upper bound value 60. So obviously upper bound value the maximum value we have to consider. So if we are adding this first item in the sense upper bound value is 76. If you are not adding this first item in the sense upper bound value was 60. So which one we will consider? So this is the maximum upper bound value. So we will continue with this node okay. Next step we need to consider second item similar way only that is If you are adding the second item that will be added as a left subtree. If you are not adding the second item that will be added as right subtree. Okay. So here this is with item 2. This is without item 2. Okay. So with item 2 in the sense what will be the weight. So here previous step we need to consider its weight and value and we have to add the consolidated weight and value. Okay. So here. Weight if you are considering in the sense previously the weight is 4. Currently if you are adding second item its weight is 7. So here we will get the weight 11. So our maximum capacity is 10 only. But if you are adding the second item we will get 11. So this is not actually feasible. Okay. Its weight will be 11. So this is not feasible. Okay. So you should not consider this node. If you are. Considering this note, this will be a dead end because it will destroy your problem constraint. Okay. So, consider without adding the second item. So, without adding the second item in the sense, here weight will be previously it is 4 plus currently we are not going to add second item. So, it is 0. So, weight is 4 only and value is previously it is 40, currently it is 0. So, 40 only. So, here weight is 4 and value is. 40. Okay. And M minus W if you are considering in the sense M is the maximum capacity. Okay. And here weight is 4 only. So, this weight we will consider. Okay. And the remaining capacity is 6. And here upper bound value is value it is 40 plus M minus W value is 6 into value by weight ratio of the next item. Currently, we are considering second item. Value by weight ratio of the next item in the sunset is 5. Okay. So here 40 plus 30. So here we will get the upper bound value 70. Okay. Since if you are adding the second item it will exceed the maximum capacity. So this is not a feasible solution. So our promising node only promising node here is this one only. So we will continue with this. So now we have considered the second item. What is next thing? Consider third item. Okay, if you are going to add the third item into the knapsack in the sense, it will be added as a left sub tree. If you are not going to add the third item in the sense, it will be considered as a right sub tree. So, this is with three and this is without three. Okay, so here with three in the sense, weight is already it is four. Okay, currently, if you are adding third item, its weight is five. So, totally nine. So, weight is nine. And value if you are considering in the sense previously value was 40 plus currently if you are adding this item its value was 25. It is 65. See here, here weight is 9 only. Okay. It is not exceeding the maximum capacity. So here our problem constraint is satisfied. So we can consider to add the third item into the NAPSAT. This is possible. Okay. So next M minus W if you are considering in the sense. M is 10 maximum capacity, W is 9 and the remaining capacity we will get it as 1. So, here value is 65 ok and the upper bound value we will calculate now. Upper bound value is V. This formula you need to remember. Okay. V is 65 plus M minus W is 1 into value by weight ratio of the next item. Currently, we are considering third item. Value by weight ratio of the fourth item we need to consider. That value is 4. Okay. So, here we will get it as 69. So, here the upper bound value is 69. If you are adding third item into the knapsack. Next step. If you are not considering to add third item into the knapsack in the sense, weight is previously it is 4. Currently, we are not considering. So, it is 4 only. Value is previously it is 40. Currently, we are not considering. So, it is 40 only. Right? So, here W is 4, value is 40 and M minus W if you are considering in the sense M is 10 minus weight is 4. So, it is 6. Okay? And the upper bound value is V. V is 40 here. 40 plus M minus W is 6 into value by weight ratio of the next item we need to consider. That is 4. Okay. So, this if we are considering in this, this is 64. So, here upper bound value we will get it as 64. Which upper bound value we need to consider this one. Okay. So, this is the maximum. upper bound value. So, we need to consider upper bound value 69. Meaning is we are going to add third item into the knapsack. Okay. Till now we have added first item, excluded second item, added third item. Next, consider fourth item. If you are considering to add fourth item into the knapsack, it will be added as a left subtree. If you are not going to consider fourth item into the knapsack in the sense, it will be added as a right subtree. Okay. So, this is width 4. and without 4. So, with 4 in the sense, weight is previously, weight if you are considering in the sense, it is 9, right? Plus, currently, if you are adding fourth item in the sense, its weight is 3, totally, we will get it as 12. What is our maximum capacity? It is 10 only. You cannot able to add 12, right? So, if you are adding fourth item, this will destroy our problem constraint. So, here, we will leave. This is not a feasible solution. Okay. So, this is not feasible. So, no need to consider to add fourth item into the knapsack. Then, without 4 in the sense, weight if you are considering in the sense previously it is 9. Currently, it is 0. So, weight is 9 only. And value if you are considering in the sense previously it is 65. Currently, it is 0. So, value is 65 only. So, here weight is 9 and value is 65 and here if you want to calculate the upper bound value, the value by weight ratio we need to consider for next element, but there is no next element, only four elements here, this is the last element. So, in that case what we have to do it in the sense the upper bound value what we have calculated in the previous step, the same thing we have to include here, right. Why we are including the same thing? Because value by weight ratio of the next item, we will not get it. This is the last element, okay. So, the upper bound value, it will reflect from the previous step only. So, this upper bound value is also 69 only and here if you are considering, this step will be considered as the optimal solution. This is the last step, right and this will be considered as the optimal solution, okay and what is our solution vector here? So, solution vector is nothing but which are all the items you have added into the knapsack that is nothing but the solution vector. So, here we have added item number 1 and we have added item number 3. Item 2 and 4 we cannot able to add it into the knapsack since it does not satisfy our problem constraint. Okay. So, here 1 comma 3 solution vector. Okay. So, this is our optimal. solution and here the upper bound value was 69. This is the final upper bound value. Okay. And this is the procedure to construct the state space tree using branch and bound technique to solve knapsack problem. Okay. And this is a binary tree. Keep in mind in traveling salesman and assignment problem the construction of state space tree is not a binary tree. Okay. But here in knapsack problem construction of state space tree is a binary tree that you need to remember okay. This video is a continuation of the previous video okay. Previous video we have shown only the steps how to calculate the upper bound value in each step by considering each item okay. but now we have implemented the state space tree the same procedure only okay for the previous video i will provide the link in the description for your reference thank you for watching this video Thank you.

Now, in this session, for the same example, we will implement the construction of the state space tree step by step. Okay. The problem is, solve the following knapsack problem using branch and bound. technique. Given the following data, here the capacity of knapsack is 10 and here they have given four items with its corresponding weight and value.

Actually, we need to find value by weight ratio and then we have to order this value by weight ratio in decreasing order. But already here in the problem itself, they have given this value by weight ratio in decreasing order only. So, no need to do that step. Suppose if they have given item weight and value in the sense Next step, we need to find the value by weight ratio and then we have to order the elements according to the value by weight ratio in decreasing order. That we have to follow.

Okay. Since already it is in decreasing order of value by weight ratio, no need to do anything. We will continue the procedure. And here in NAVSAC problem using branch and bound technique, we need to calculate the upper bound value in each step. And the upper bound value we will calculate with the help of the formula uv equal to v plus m minus w into vi plus 1 divided by wi plus 1. v is nothing but the total value of all the items added into the knapsack.

And m is the maximum capacity and w is total weights of all the objects placed into the knapsack. And vi plus 1 divided by wi plus 1 this is the value by weight ratio of the next item. Suppose if we are considering first item in the sense in that step we need to consider value by weight ratio of the next item. So this is a formula to calculate the upper bound value.

Now with this we will implement the construction of the state space tree. In knapsack problem using branch and bound technique the construction of the state space tree is unique. That is the state space tree will be a binary tree. Okay only two nodes will be there.

Left subtree and right subtree. Left subtree represents if you are considering any item to include it into the knapsack bag in the sense that item we will place as a left subtree. Suppose if you are not going to consider the particular item we are excluding that item in the sense that will be added as a right subtree and here the state space tree is a binary tree only.

Each node will have at most maximum two children's one. So, initial state space tree is we have to consider this is the 0th level without considering any item that is the initial stage and here w is 0 and v is also 0 and what is the upper bound value? So, upper bound is values this formula we have to implement ok.

So, value is 0 plus m minus w, m is the maximum capacity. So, 10 minus w is also 0. into value by weight ratio of the next item that is 0th item we are considering. So value by weight ratio we need to consider the first item okay so it is 10. So here we will get the upper bound value 100. So this is the initial stage and here this will be considered as item 0 okay.

Next with this node we will continue to construct the next level components. So next level consider item 1. Already I said if you are including item 1 that will be added as a left subtree. If you are not including item 1 that will be added as a right subtree.

Okay. So in both the cases we need to find the upper bound value. So here since we are considering the first item its weight and value we need to include. Weight is 4 and value is 40. Next we need to calculate the upper bound value.

So here. M minus W, M value is 10, W is 4 and the remaining capacity is 6. So, meaning is if you are including this item into the NAVSAT, it will not destroy the problem constraint. What is the problem constraint? There are two constraints here.

One is whenever you are adding any item into the NAVSAT, it should not exceed the maximum capacity. So, here the maximum capacity is 10 and also it should maximize the profit. At the end since we are calculating the upper bound value at the end obviously we will get the upper bound value only. So profit will be maximized only.

So this is M minus W. Then the upper bound is value, value is 40 plus m minus w is 6 into value by weight ratio of the next item. Now we are considering first item, value by weight ratio of the next item is 6. So here the upper bound value we will get it as 76. Okay, suppose if you are not going to consider, so this is with item 1 and this is without item 1. Suppose if you are not going to consider this first item to add it into the knapsack in the sense weight will be 0 and also value will be 0 and m minus w if you are considering in the sense 10 minus 0. So this is 10 only right. So here upper bound value is value is 0 plus m minus w this value is 10 into value by weight ratio of the next item it is 6. So here we will get the upper bound value 60. So obviously upper bound value the maximum value we have to consider. So if we are adding this first item in the sense upper bound value is 76. If you are not adding this first item in the sense upper bound value was 60. So which one we will consider?

So this is the maximum upper bound value. So we will continue with this node okay. Next step we need to consider second item similar way only that is If you are adding the second item that will be added as a left subtree. If you are not adding the second item that will be added as right subtree. Okay.

So here this is with item 2. This is without item 2. Okay. So with item 2 in the sense what will be the weight. So here previous step we need to consider its weight and value and we have to add the consolidated weight and value.

Okay. So here. Weight if you are considering in the sense previously the weight is 4. Currently if you are adding second item its weight is 7. So here we will get the weight 11. So our maximum capacity is 10 only. But if you are adding the second item we will get 11. So this is not actually feasible. Okay.

Its weight will be 11. So this is not feasible. Okay. So you should not consider this node.

If you are. Considering this note, this will be a dead end because it will destroy your problem constraint. Okay. So, consider without adding the second item. So, without adding the second item in the sense, here weight will be previously it is 4 plus currently we are not going to add second item.

So, it is 0. So, weight is 4 only and value is previously it is 40, currently it is 0. So, 40 only. So, here weight is 4 and value is. 40. Okay. And M minus W if you are considering in the sense M is the maximum capacity.

Okay. And here weight is 4 only. So, this weight we will consider.

Okay. And the remaining capacity is 6. And here upper bound value is value it is 40 plus M minus W value is 6 into value by weight ratio of the next item. Currently, we are considering second item. Value by weight ratio of the next item in the sunset is 5. Okay. So here 40 plus 30. So here we will get the upper bound value 70. Okay.

Since if you are adding the second item it will exceed the maximum capacity. So this is not a feasible solution. So our promising node only promising node here is this one only.

So we will continue with this. So now we have considered the second item. What is next thing?

Consider third item. Okay, if you are going to add the third item into the knapsack in the sense, it will be added as a left sub tree. If you are not going to add the third item in the sense, it will be considered as a right sub tree.

So, this is with three and this is without three. Okay, so here with three in the sense, weight is already it is four. Okay, currently, if you are adding third item, its weight is five.

So, totally nine. So, weight is nine. And value if you are considering in the sense previously value was 40 plus currently if you are adding this item its value was 25. It is 65. See here, here weight is 9 only. Okay.

It is not exceeding the maximum capacity. So here our problem constraint is satisfied. So we can consider to add the third item into the NAPSAT. This is possible.

Okay. So next M minus W if you are considering in the sense. M is 10 maximum capacity, W is 9 and the remaining capacity we will get it as 1. So, here value is 65 ok and the upper bound value we will calculate now.

Upper bound value is V. This formula you need to remember. Okay. V is 65 plus M minus W is 1 into value by weight ratio of the next item. Currently, we are considering third item. Value by weight ratio of the fourth item we need to consider.

That value is 4. Okay. So, here we will get it as 69. So, here the upper bound value is 69. If you are adding third item into the knapsack. Next step. If you are not considering to add third item into the knapsack in the sense, weight is previously it is 4. Currently, we are not considering.

So, it is 4 only. Value is previously it is 40. Currently, we are not considering. So, it is 40 only. Right? So, here W is 4, value is 40 and M minus W if you are considering in the sense M is 10 minus weight is 4. So, it is 6. Okay?

And the upper bound value is V. V is 40 here. 40 plus M minus W is 6 into value by weight ratio of the next item we need to consider. That is 4. Okay.

So, this if we are considering in this, this is 64. So, here upper bound value we will get it as 64. Which upper bound value we need to consider this one. Okay. So, this is the maximum.

upper bound value. So, we need to consider upper bound value 69. Meaning is we are going to add third item into the knapsack. Okay. Till now we have added first item, excluded second item, added third item. Next, consider fourth item.

If you are considering to add fourth item into the knapsack, it will be added as a left subtree. If you are not going to consider fourth item into the knapsack in the sense, it will be added as a right subtree. Okay.

So, this is width 4. and without 4. So, with 4 in the sense, weight is previously, weight if you are considering in the sense, it is 9, right? Plus, currently, if you are adding fourth item in the sense, its weight is 3, totally, we will get it as 12. What is our maximum capacity? It is 10 only.

You cannot able to add 12, right? So, if you are adding fourth item, this will destroy our problem constraint. So, here, we will leave. This is not a feasible solution. Okay.

So, this is not feasible. So, no need to consider to add fourth item into the knapsack. Then, without 4 in the sense, weight if you are considering in the sense previously it is 9. Currently, it is 0. So, weight is 9 only.

And value if you are considering in the sense previously it is 65. Currently, it is 0. So, value is 65 only. So, here weight is 9 and value is 65 and here if you want to calculate the upper bound value, the value by weight ratio we need to consider for next element, but there is no next element, only four elements here, this is the last element. So, in that case what we have to do it in the sense the upper bound value what we have calculated in the previous step, the same thing we have to include here, right. Why we are including the same thing? Because value by weight ratio of the next item, we will not get it.

This is the last element, okay. So, the upper bound value, it will reflect from the previous step only. So, this upper bound value is also 69 only and here if you are considering, this step will be considered as the optimal solution. This is the last step, right and this will be considered as the optimal solution, okay and what is our solution vector here?

So, solution vector is nothing but which are all the items you have added into the knapsack that is nothing but the solution vector. So, here we have added item number 1 and we have added item number 3. Item 2 and 4 we cannot able to add it into the knapsack since it does not satisfy our problem constraint. Okay.

So, here 1 comma 3 solution vector. Okay. So, this is our optimal.

solution and here the upper bound value was 69. This is the final upper bound value. Okay. And this is the procedure to construct the state space tree using branch and bound technique to solve knapsack problem.

Okay. And this is a binary tree. Keep in mind in traveling salesman and assignment problem the construction of state space tree is not a binary tree. Okay.

But here in knapsack problem construction of state space tree is a binary tree that you need to remember okay. This video is a continuation of the previous video okay. Previous video we have shown only the steps how to calculate the upper bound value in each step by considering each item okay.

but now we have implemented the state space tree the same procedure only okay for the previous video i will provide the link in the description for your reference thank you for watching this video Thank you.

Transcript for:Knapsack Problem - Branch and Bound Technique Summary

Transcript for:
Knapsack Problem - Branch and Bound Technique Summary