{"id":377,"date":"2024-02-02T10:38:58","date_gmt":"2024-02-02T10:38:58","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=377"},"modified":"2025-03-13T13:32:33","modified_gmt":"2025-03-13T13:32:33","slug":"branch-and-bound","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=377","title":{"rendered":"Branch and Bound"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li><strong>How does the branch and bound method work?<\/strong><\/li>\n\n\n\n<li><strong>Live node, e-node, and dead node<\/strong><\/li>\n\n\n\n<li><strong>FIFO-BB and LIFO-BB<\/strong><\/li>\n\n\n\n<li><strong><a href=\"#jobseq\" data-type=\"internal\" data-id=\"#jobseq\">Job Sequencing with Deadlines using Branch and Bound.<\/a><\/strong><\/li>\n\n\n\n<li><a href=\"#Seq\" data-type=\"internal\" data-id=\"#Seq\"><strong>How does it work (FIFOBB for Job Sequencing)?<\/strong><\/a><\/li>\n\n\n\n<li><strong><a href=\"#BBKNAP\" data-type=\"internal\" data-id=\"#BBKNAP\">Branch and bound  solution for 0-1 knapsack problem<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#BBTSP\" data-type=\"internal\" data-id=\"#BBTSP\">Branch and bound solution for Travelling Sales Person (TSP) problem<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#BBNQUEEN\" data-type=\"internal\" data-id=\"#BBNQUEEN\">Branch and bound solution for N-Queen problem<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#Expl\">Explanation of NQUEEN, Knapsack &amp; Job Assignment solution using Branch and Bound<\/a><\/strong><\/li>\n\n\n\n<li><strong>Least cost branch and bound (LC-BB)<\/strong><\/li>\n\n\n\n<li><strong>A* algorithm is LC-BB<\/strong><\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/BB_Definition-1024x324.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/BB_DEF2-1024x213.png\" alt=\"\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/BB_DEF3.png\" alt=\"\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1-1024x576.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"jobseq\"><strong>Job Sequencing with Deadlines using Branch and Bound<\/strong>.<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"724\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/BB_JOB_SELECTION-3_pages-to-jpg-0001-724x1024.jpg\" alt=\"\" class=\"wp-image-1763\" style=\"width:997px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/BB_JOB_SELECTION-3_pages-to-jpg-0001-724x1024.jpg 724w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/BB_JOB_SELECTION-3_pages-to-jpg-0001-212x300.jpg 212w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/BB_JOB_SELECTION-3_pages-to-jpg-0001-768x1087.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/BB_JOB_SELECTION-3_pages-to-jpg-0001-1085x1536.jpg 1085w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/BB_JOB_SELECTION-3_pages-to-jpg-0001.jpg 1240w\" sizes=\"auto, (max-width: 724px) 100vw, 724px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"Seq\"><strong>How does FIFO BB work for job sequencing with deadlines, penalties, and execution time?<\/strong><\/h3>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Job Sequencing with Deadline | Branch and Bound Method Explained!\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/o5JA2Ps4zLg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"BBKNAP\"><strong>Solving 0-1 Knapsack using Branch and Bound<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image is-resized size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-02-at-13.47.43-2-737x1024.jpeg\" alt=\"\" style=\"width:997px;height:auto\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image is-resized size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-02-at-13.47.43-1-1-732x1024.jpeg\" alt=\"\" style=\"width:996px;height:auto\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">C code for solving 0-1 Knapsack using Branch and Bound<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\n\/\/ Structure to store the item information\ntypedef struct {\n    int weight;  \/\/ Weight of the item\n    int value;   \/\/ Value of the item\n    float ratio; \/\/ Value-to-weight ratio of the item (used for sorting)\n} Item;\n\n\/\/ Structure to store the state of the node in the search tree\ntypedef struct {\n    int level;   \/\/ The current level of the node (which item is being considered)\n    int profit;  \/\/ The current profit obtained by including\/excluding items\n    int weight;  \/\/ The total weight of the items included so far\n    float bound; \/\/ The upper bound of the profit that can be achieved from this node\n} Node;\n\n\/\/ Function to calculate the bound (upper bound) for a node in the search tree\nfloat bound(Node u, int n, int W, Item items&#91;]) {\n    \/\/ If the current node's weight is more than the capacity, return 0 (no profit)\n    if (u.weight &gt;= W) return 0;\n\n    \/\/ Initialize the result as the profit of the current node\n    float result = u.profit;\n\n    \/\/ Start from the next item in the list\n    int j = u.level + 1;\n    int totalWeight = u.weight;\n\n    \/\/ Include items greedily until the knapsack is full or we run out of items\n    while (j &lt; n &amp;&amp; totalWeight + items&#91;j].weight &lt;= W) {\n        totalWeight += items&#91;j].weight;  \/\/ Add the item to the knapsack\n        result += items&#91;j].value;        \/\/ Add the value of the item\n        j++;  \/\/ Move to the next item\n    }\n\n    \/\/ If there are still items left, take the fractional part of the next item (fractional knapsack)\n    if (j &lt; n) {\n        result += (W - totalWeight) * items&#91;j].ratio;  \/\/ Add fraction of the next item\n    }\n\n    return result;  \/\/ Return the upper bound for the current node\n}\n\n\/\/ Comparison function to sort items based on their value-to-weight ratio (descending order)\nint compare(const void *a, const void *b) {\n    \/\/ Cast the void pointers to Item pointers to access their value-to-weight ratio\n    float r1 = ((Item*)a)-&gt;ratio;\n    float r2 = ((Item*)b)-&gt;ratio;\n    \n    \/\/ Compare the ratios in descending order\n    return (r1 &lt; r2) - (r1 &gt; r2);  \/\/ Return 1 if r1 &lt; r2, -1 if r1 &gt; r2, 0 if equal\n}\n\n\/\/ Function to solve the Knapsack problem using Branch and Bound\nint knapsack(int n, int W, Item items&#91;]) {\n    \/\/ Calculate value-to-weight ratio for each item\n    for (int i = 0; i &lt; n; i++) {\n        items&#91;i].ratio = (float)items&#91;i].value \/ items&#91;i].weight;  \/\/ Value per unit weight\n    }\n\n    \/\/ Sort the items based on value-to-weight ratio in descending order\n    qsort(items, n, sizeof(Item), compare);\n\n    \/\/ Initialize the root node with no items considered yet\n    Node u, v;\n    u.level = -1;       \/\/ Start at level -1 (no item considered yet)\n    u.profit = 0;       \/\/ No profit initially\n    u.weight = 0;       \/\/ No weight initially\n    u.bound = bound(u, n, W, items);  \/\/ Calculate the upper bound of profit at the root\n\n    \/\/ Create a queue for BFS-like traversal of the search tree (node processing)\n    Node queue&#91;1000];\n    int front = 0, rear = 0;  \/\/ Initialize the queue (front and rear pointers)\n    queue&#91;rear++] = u;        \/\/ Add the root node to the queue\n\n    int maxProfit = 0;  \/\/ Variable to store the maximum profit found so far\n\n    \/\/ Process nodes in the queue until the queue is empty\n    while (front != rear) {\n        u = queue&#91;front++];  \/\/ Get the next node from the queue\n\n        \/\/ If the upper bound of the current node is less than the best solution found, prune the node\n        if (u.bound &lt;= maxProfit) continue;\n\n        \/\/ Case 1: Include the next item (item at level u.level + 1)\n        v.level = u.level + 1;  \/\/ Move to the next level in the decision tree\n        v.weight = u.weight + items&#91;v.level].weight;  \/\/ Add the weight of the next item\n        v.profit = u.profit + items&#91;v.level].value;   \/\/ Add the value of the next item\n\n        \/\/ If the new node is valid (does not exceed the knapsack capacity) and improves the solution, update maxProfit\n        if (v.weight &lt;= W &amp;&amp; v.profit &gt; maxProfit) {\n            maxProfit = v.profit;  \/\/ Update the maximum profit\n        }\n\n        \/\/ Calculate the upper bound for the \"include\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ If the bound for this branch is greater than the best known solution, add it to the queue\n        if (v.bound &gt; maxProfit) {\n            queue&#91;rear++] = v;  \/\/ Add this node to the queue\n        }\n\n        \/\/ Case 2: Exclude the next item (move to the next level without including the item)\n        v.weight = u.weight;  \/\/ Do not include the weight of the next item\n        v.profit = u.profit;  \/\/ Do not add the value of the next item\n\n        \/\/ Calculate the upper bound for the \"exclude\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ If the bound for this branch is greater than the best known solution, add it to the queue\n        if (v.bound &gt; maxProfit) {\n            queue&#91;rear++] = v;  \/\/ Add this node to the queue\n        }\n    }\n    return maxProfit;  \/\/ Return the maximum profit found\n}\nint main() {\n    int n, W;\n    \/\/ Input the number of items and the capacity of the knapsack\n    printf(\"Enter the number of items: \");\n    scanf(\"%d\", &amp;n);\n    printf(\"Enter the capacity of the knapsack: \");\n    scanf(\"%d\", &amp;W);\n    \/\/ Declare an array to store the items\n    Item items&#91;n];\n    \/\/ Input the weight and value of each item\n    printf(\"Enter the weight and value of each item:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        scanf(\"%d %d\", &amp;items&#91;i].weight, &amp;items&#91;i].value);\n    }\n    \/\/ Call the knapsack function using Branch and Bound to find the maximum profit\n    int maxProfit = knapsack(n, W, items);\n    \/\/ Output the maximum value that can be obtained with the given capacity\n    printf(\"The maximum value that can be obtained is: %d\\n\", maxProfit);\n    return 0;  \/\/ Return 0 to indicate successful program execution\n}\nOutput :\nEnter the number of items: 4\nEnter the capacity of the knapsack: 50\nEnter the weight and value of each item:\n10 60\n20 100\n30 110\n12 14\nThe maximum value that can be obtained is: 210\n\nProcess returned 0 (0x0)   execution time : 59.469 s\nPress any key to continue.\n\n\n\n<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/Track which items are included in the optimal solution.\n\/\/Display the items picked at the end.<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\/\/ Structure to store the item information\ntypedef struct {\n    int weight;  \/\/ Weight of the item\n    int value;   \/\/ Value of the item\n    float ratio; \/\/ Value-to-weight ratio of the item (used for sorting)\n} Item;\n\/\/ Structure to store the state of the node in the search tree\ntypedef struct {\n    int level;   \/\/ The current level of the node (which item is being considered)\n    int profit;  \/\/ The current profit obtained by including\/excluding items\n    int weight;  \/\/ The total weight of the items included so far\n    float bound; \/\/ The upper bound of the profit that can be achieved from this node\n    int *included; \/\/ Array to track the items included in the knapsack at this node\n} Node;\n\n\/\/ Function to calculate the bound (upper bound) for a node in the search tree\nfloat bound(Node u, int n, int W, Item items&#91;]) {\n    \/\/ If the current node's weight is more than the capacity, return 0 (no profit)\n    if (u.weight &gt;= W) return 0;\n    \/\/ Initialize the result as the profit of the current node\n    float result = u.profit;\n    \/\/ Start from the next item in the list\n    int j = u.level + 1;\n    int totalWeight = u.weight;\n    \/\/ Include items greedily until the knapsack is full or we run out of items\n    while (j &lt; n &amp;&amp; totalWeight + items&#91;j].weight &lt;= W) {\n        totalWeight += items&#91;j].weight;  \/\/ Add the item to the knapsack\n        result += items&#91;j].value;        \/\/ Add the value of the item\n        j++;  \/\/ Move to the next item\n    }\n\n    \/\/ If there are still items left, take the fractional part of the next item (fractional knapsack)\n    if (j &lt; n) {\n        result += (W - totalWeight) * items&#91;j].ratio;  \/\/ Add fraction of the next item\n    }\n    return result;  \/\/ Return the upper bound for the current node\n}\n\/\/ Comparison function to sort items based on their value-to-weight ratio (descending order)\nint compare(const void *a, const void *b) {\n    \/\/ Cast the void pointers to Item pointers to access their value-to-weight ratio\n    float r1 = ((Item*)a)-&gt;ratio;\n    float r2 = ((Item*)b)-&gt;ratio;\n        \/\/ Compare the ratios in descending order\n    return (r1 &lt; r2) - (r1 &gt; r2);  \/\/ Return 1 if r1 &lt; r2, -1 if r1 &gt; r2, 0 if equal\n}\n\/\/ Function to solve the Knapsack problem using Branch and Bound\nint knapsack(int n, int W, Item items&#91;]) {\n    \/\/ Calculate value-to-weight ratio for each item\n    for (int i = 0; i &lt; n; i++) {\n        items&#91;i].ratio = (float)items&#91;i].value \/ items&#91;i].weight;  \/\/ Value per unit weight\n    }\n\n    \/\/ Sort the items based on value-to-weight ratio in descending order\n    qsort(items, n, sizeof(Item), compare);\n\n    \/\/ Initialize the root node with no items considered yet\n    Node u, v;\n    u.level = -1;       \/\/ Start at level -1 (no item considered yet)\n    u.profit = 0;       \/\/ No profit initially\n    u.weight = 0;       \/\/ No weight initially\n    u.bound = bound(u, n, W, items);  \/\/ Calculate the upper bound of profit at the root\n    u.included = (int*)calloc(n, sizeof(int));  \/\/ Allocate memory to track included items\n\n    \/\/ Create a queue for BFS-like traversal of the search tree (node processing)\n    Node queue&#91;1000];\n    int front = 0, rear = 0;  \/\/ Initialize the queue (front and rear pointers)\n    queue&#91;rear++] = u;        \/\/ Add the root node to the queue\n\n    int maxProfit = 0;  \/\/ Variable to store the maximum profit found so far\n    Node bestSolution;  \/\/ Store the best solution (with selected items)\n\n    \/\/ Process nodes in the queue until the queue is empty\n    while (front != rear) {\n        u = queue&#91;front++];  \/\/ Get the next node from the queue\n\n        \/\/ If the upper bound of the current node is less than the best solution found, prune the node\n        if (u.bound &lt;= maxProfit) continue;\n\n        \/\/ Case 1: Include the next item (item at level u.level + 1)\n        v.level = u.level + 1;  \/\/ Move to the next level in the decision tree\n        v.weight = u.weight + items&#91;v.level].weight;  \/\/ Add the weight of the next item\n        v.profit = u.profit + items&#91;v.level].value;   \/\/ Add the value of the next item\n        v.included = (int*)malloc(n * sizeof(int));  \/\/ Allocate memory for included items\n        memcpy(v.included, u.included, n * sizeof(int));  \/\/ Copy the inclusion array\n        \/\/ Mark the item as included\n        v.included&#91;v.level] = 1;\n        \/\/ If the new node is valid (does not exceed the knapsack capacity) and improves the solution, update maxProfit\n        if (v.weight &lt;= W &amp;&amp; v.profit &gt; maxProfit) {\n            maxProfit = v.profit;  \/\/ Update the maximum profit\n            bestSolution = v;      \/\/ Store the best solution found so far\n        }\n        \/\/ Calculate the upper bound for the \"include\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ If the bound for this branch is greater than the best known solution, add it to the queue\n        if (v.bound &gt; maxProfit) {\n            queue&#91;rear++] = v;  \/\/ Add this node to the queue\n        }\n\n        \/\/ Case 2: Exclude the next item (move to the next level without including the item)\n        v.weight = u.weight;  \/\/ Do not include the weight of the next item\n        v.profit = u.profit;  \/\/ Do not add the value of the next item\n        v.included = (int*)malloc(n * sizeof(int));  \/\/ Allocate memory for included items\n        memcpy(v.included, u.included, n * sizeof(int));  \/\/ Copy the inclusion array\n        \/\/ Mark the item as excluded\n        v.included&#91;v.level] = 0;\n        \/\/ Calculate the upper bound for the \"exclude\" branch\n        v.bound = bound(v, n, W, items);\n        \/\/ If the bound for this branch is greater than the best known solution, add it to the queue\n        if (v.bound &gt; maxProfit) {\n            queue&#91;rear++] = v;  \/\/ Add this node to the queue\n        }\n    }\n    \/\/ Return the maximum profit found and the best solution\n    \/\/ Output the selected items\n    printf(\"\\nItems included in the knapsack:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        if (bestSolution.included&#91;i]) {\n            printf(\"Item %d (Weight: %d, Value: %d)\\n\", i+1, items&#91;i].weight, items&#91;i].value);\n        }\n    }\n\n    \/\/ Clean up allocated memory\n    free(u.included);\n    free(bestSolution.included);\n\n    return maxProfit;  \/\/ Return the maximum profit found\n}\n\nint main() {\n    int n, W;\n\n    \/\/ Input the number of items and the capacity of the knapsack\n    printf(\"Enter the number of items: \");\n    scanf(\"%d\", &amp;n);\n    printf(\"Enter the capacity of the knapsack: \");\n    scanf(\"%d\", &amp;W);\n\n    \/\/ Declare an array to store the items\n    Item items&#91;n];\n\n    \/\/ Input the weight and value of each item\n    printf(\"Enter the weight and value of each item:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        scanf(\"%d %d\", &amp;items&#91;i].weight, &amp;items&#91;i].value);\n    }\n\n    \/\/ Call the knapsack function using Branch and Bound to find the maximum profit\n    int maxProfit = knapsack(n, W, items);\n\n    \/\/ Output the maximum value that can be obtained with the given capacity\n    printf(\"\\nThe maximum value that can be obtained is: %d\\n\", maxProfit);\n\n    return 0;  \/\/ Return 0 to indicate successful program execution\n}<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/C++ code WITH STRUCTURE<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\n#include &lt;queue&gt;\nusing namespace std;\n\n\/\/ Structure to represent an item with its weight, value, and value-to-weight ratio\nstruct Item {\n    int weight;\n    int value;\n    float ratio; \/\/ Value-to-weight ratio\n};\n\n\/\/ Structure to represent a node in the search tree\nstruct Node {\n    int level;  \/\/ Current level (which item is being considered)\n    int profit; \/\/ Current profit obtained\n    int weight; \/\/ Current total weight\n    float bound; \/\/ Upper bound on the profit achievable from this node\n};\n\n\/\/ Function to calculate the upper bound for a node\nfloat bound(Node u, int n, int W, Item items&#91;]) {\n    \/\/ If the current weight exceeds the knapsack capacity, no profit is possible\n    if (u.weight &gt;= W)\n        return 0;\n\n    float result = u.profit;\n    int j = u.level + 1;\n    int totalWeight = u.weight;\n\n    \/\/ Greedily include items until the knapsack is full or all items are considered\n    while (j &lt; n &amp;&amp; totalWeight + items&#91;j].weight &lt;= W) {\n        totalWeight += items&#91;j].weight;\n        result += items&#91;j].value;\n        j++;\n    }\n\n    \/\/ If there's still space in the knapsack, include a fraction of the next item\n    if (j &lt; n) {\n        result += (W - totalWeight) * items&#91;j].ratio;\n    }\n\n    return result;\n}\n\n\/\/ Comparison function to sort items by their value-to-weight ratio in descending order\nbool compare(Item a, Item b) {\n    return a.ratio &gt; b.ratio;\n}\n\n\/\/ Function to solve the Knapsack problem using Branch and Bound\nint knapsack(int n, int W, Item items&#91;]) {\n    \/\/ Calculate value-to-weight ratio for each item\n    for (int i = 0; i &lt; n; i++) {\n        items&#91;i].ratio = (float)items&#91;i].value \/ items&#91;i].weight;\n    }\n\n    \/\/ Sort items in descending order of their value-to-weight ratio\n    sort(items, items + n, compare);\n\n    \/\/ Initialize the root node\n    Node u, v;\n    u.level = -1;\n    u.profit = 0;\n    u.weight = 0;\n    u.bound = bound(u, n, W, items);\n\n    \/\/ Create a queue to perform BFS-like traversal of the search tree\n    queue&lt;Node&gt; q;\n    q.push(u);\n\n    int maxProfit = 0; \/\/ To store the maximum profit found so far\n\n    \/\/ Process nodes in the queue until it becomes empty\n    while (!q.empty()) {\n        u = q.front();\n        q.pop();\n\n        \/\/ Prune the node if its upper bound is less than or equal to the current best profit\n        if (u.bound &lt;= maxProfit)\n            continue;\n\n        \/\/ Case 1: Include the next item\n        v.level = u.level + 1;\n        v.weight = u.weight + items&#91;v.level].weight;\n        v.profit = u.profit + items&#91;v.level].value;\n\n        \/\/ If the new node is feasible and has a better profit, update the maximum profit\n        if (v.weight &lt;= W &amp;&amp; v.profit &gt; maxProfit) {\n            maxProfit = v.profit;\n        }\n\n        \/\/ Calculate the upper bound for the \"include\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ Add the \"include\" node to the queue if its bound is promising\n        if (v.bound &gt; maxProfit) {\n            q.push(v);\n        }\n\n        \/\/ Case 2: Exclude the next item\n        v.weight = u.weight;\n        v.profit = u.profit;\n\n        \/\/ Calculate the upper bound for the \"exclude\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ Add the \"exclude\" node to the queue if its bound is promising\n        if (v.bound &gt; maxProfit) {\n            q.push(v);\n        }\n    }\n\n    return maxProfit;\n}\n\nint main() {\n    int n, W;\n\n    cout &lt;&lt; \"Enter the number of items: \";\n    cin &gt;&gt; n;\n    cout &lt;&lt; \"Enter the capacity of the knapsack: \";\n    cin &gt;&gt; W;\n\n    Item items&#91;n];\n\n    cout &lt;&lt; \"Enter the weight and value of each item:\\n\";\n    for (int i = 0; i &lt; n; i++) {\n        cin &gt;&gt; items&#91;i].weight &gt;&gt; items&#91;i].value;\n    }\n\n    int maxProfit = knapsack(n, W, items);\n\n    cout &lt;&lt; \"The maximum value that can be obtained is: \" &lt;&lt; maxProfit &lt;&lt; endl;\n\n    return 0;\n}\nEnter the number of items: 3\nEnter the capacity of the knapsack: 10\nEnter the weight and value of each item:\n2 4\n5 5\n3 6\nThe maximum value that can be obtained is: 15\n\nProcess returned 0 (0x0)   execution time : 31.722 s\nPress any key to continue.\n<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/C++ code with class and vector STL<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\n#include &lt;queue&gt;\n#include &lt;vector&gt;\n\nusing namespace std;\n\n\/\/ Class to represent an item with its weight, value, and value-to-weight ratio\nclass Item {\npublic:\n    int weight;\n    int value;\n    float ratio; \/\/ Value-to-weight ratio\n\n    Item(int w, int v) : weight(w), value(v), ratio((float)v \/ w) {}\n};\n\n\/\/ Structure to represent a node in the search tree\nstruct Node {\n    int level;  \/\/ Current level (which item is being considered)\n    int profit; \/\/ Current profit obtained\n    int weight; \/\/ Current total weight\n    float bound; \/\/ Upper bound on the profit achievable from this node\n};\n\n\/\/ Function to calculate the upper bound for a node\nfloat bound(Node u, int n, int W, const vector&lt;Item&gt;&amp; items) {\n    if (u.weight &gt;= W) \n        return 0;\n\n    float result = u.profit; \n    int j = u.level + 1; \n    int totalWeight = u.weight;\n\n    while (j &lt; n &amp;&amp; totalWeight + items&#91;j].weight &lt;= W) { \n        totalWeight += items&#91;j].weight;\n        result += items&#91;j].value;\n        j++;\n    }\n\n    if (j &lt; n) {\n        result += (W - totalWeight) * items&#91;j].ratio; \n    }\n\n    return result;\n}\n\n\/\/ Comparison function to sort items by their value-to-weight ratio in descending order\nbool compare(const Item&amp; a, const Item&amp; b) {\n    return a.ratio &gt; b.ratio;\n}\n\n\/\/ Function to solve the Knapsack problem using Branch and Bound \nint knapsack(int n, int W, const vector&lt;Item&gt;&amp; items) {\n    \/\/ Sort items in descending order of their value-to-weight ratio\n    sort(items.begin(), items.end(), compare);\n\n    \/\/ Initialize the root node \n    Node u, v;\n    u.level = -1;\n    u.profit = 0;\n    u.weight = 0;\n    u.bound = bound(u, n, W, items);\n\n    \/\/ Create a queue to perform BFS-like traversal of the search tree\n    queue&lt;Node&gt; q;\n    q.push(u); \n\n    int maxProfit = 0; \/\/ To store the maximum profit found so far\n\n    \/\/ Process nodes in the queue until it becomes empty\n    while (!q.empty()) {\n        u = q.front();\n        q.pop();\n\n        \/\/ Prune the node if its upper bound is less than or equal to the current best profit\n        if (u.bound &lt;= maxProfit) \n            continue;\n\n        \/\/ Case 1: Include the next item \n        v.level = u.level + 1;\n        v.weight = u.weight + items&#91;v.level].weight;\n        v.profit = u.profit + items&#91;v.level].value;\n\n        \/\/ If the new node is feasible and has a better profit, update the maximum profit\n        if (v.weight &lt;= W &amp;&amp; v.profit &gt; maxProfit) {\n            maxProfit = v.profit;\n        }\n\n        \/\/ Calculate the upper bound for the \"include\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ Add the \"include\" node to the queue if its bound is promising\n        if (v.bound &gt; maxProfit) {\n            q.push(v);\n        }\n\n        \/\/ Case 2: Exclude the next item\n        v.weight = u.weight;\n        v.profit = u.profit;\n\n        \/\/ Calculate the upper bound for the \"exclude\" branch\n        v.bound = bound(v, n, W, items);\n\n        \/\/ Add the \"exclude\" node to the queue if its bound is promising\n        if (v.bound &gt; maxProfit) {\n            q.push(v);\n        }\n    }\n\n    return maxProfit;\n}\n\nint main() {\n    int n, W;\n\n    cout &lt;&lt; \"Enter the number of items: \";\n    cin &gt;&gt; n;\n    cout &lt;&lt; \"Enter the capacity of the knapsack: \";\n    cin &gt;&gt; W;\n\n    vector&lt;Item&gt; items; \n\n    cout &lt;&lt; \"Enter the weight and value of each item:\\n\";\n    for (int i = 0; i &lt; n; i++) {\n        int w, v;\n        cin &gt;&gt; w &gt;&gt; v;\n        items.push_back(Item(w, v)); \n    }\n\n    int maxProfit = knapsack(n, W, items);\n\n    cout &lt;&lt; \"The maximum value that can be obtained is: \" &lt;&lt; maxProfit &lt;&lt; endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"BBTSP\"><strong>Branch and bound for Travelling Sales Person (TSP) problem <\/strong><\/h2>\n\n\n\n<p>The travelling salesperson problem, also known as <strong>travelling salesman problem (TSP), <\/strong>asks the following question: &#8220;Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?&#8221; It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.<\/p>\n\n\n\n<p>The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.<\/p>\n\n\n\n<figure class=\"wp-block-image is-resized size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-730x1024.jpeg\" alt=\"\" style=\"width:995px;height:auto\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"755\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-1-755x1024.jpeg\" alt=\"\" class=\"wp-image-413\" style=\"width:1200px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-1-755x1024.jpeg 755w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-1-221x300.jpeg 221w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-1-768x1042.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-1-1132x1536.jpeg 1132w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-06-at-20.11.50-1.jpeg 1179w\" sizes=\"auto, (max-width: 755px) 100vw, 755px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"717\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-1-717x1024.jpeg\" alt=\"\" class=\"wp-image-450\" style=\"width:1204px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-1-717x1024.jpeg 717w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-1-210x300.jpeg 210w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-1-768x1097.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-1.jpeg 972w\" sizes=\"auto, (max-width: 717px) 100vw, 717px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"723\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/tspbb2fig-723x1024.png\" alt=\"\" class=\"wp-image-473\" style=\"width:1198px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/tspbb2fig-723x1024.png 723w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/tspbb2fig-212x300.png 212w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/tspbb2fig-768x1088.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/tspbb2fig.png 1076w\" sizes=\"auto, (max-width: 723px) 100vw, 723px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"727\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-727x1024.jpeg\" alt=\"\" class=\"wp-image-452\" style=\"width:1199px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-727x1024.jpeg 727w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-213x300.jpeg 213w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-768x1082.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1.jpeg 1056w\" sizes=\"auto, (max-width: 727px) 100vw, 727px\" \/><\/figure>\n\n\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solving 4 queen problem using Branch and Bound<\/strong><\/h2>\n\n\n\n<p>Imagine a game of chess where you&#8217;re tasked with placing queens on a chessboard. The catch? You can&#8217;t place them where they&#8217;ll threaten each other. This puzzle is known as the N Queens problem, where you have to position <strong>N queens<\/strong> on an N\u00d7N chessboard without any of them being able to attack each other. So, no sharing rows, columns, or diagonals!<\/p>\n\n\n\n<p>Now, let&#8217;s talk about two ways to tackle this challenge: backtracking and Branch and Bound.<\/p>\n\n\n\n<p>In the backtracking method, you start by placing queens one by one, column by column. When you place a queen in a column, you check if it clashes with any previously placed queens. If it does, you backtrack and try another spot. Simple, &nbsp;right?<\/p>\n\n\n\n<p>Now, Branch and Bound takes a slightly different approach. It&#8217;s like peeking ahead in a maze.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/C code for TSP\n#include &lt;stdio.h&gt;\n#include &lt;limits.h&gt;\n\n#define MAX_CITIES 20\n\nint dist&#91;MAX_CITIES]&#91;MAX_CITIES]; \/\/ Matrix to store distances between cities\nint visited&#91;MAX_CITIES]; \/\/ Array to keep track of visited cities\nint min_cost = INT_MAX; \/\/ Minimum cost of the tour\n\n\/\/ Function to calculate the lower bound for a given path\nint lower_bound(int city) {\n    int i, j;\n    int lb = 0;\n\n    for (i = 0; i &lt; MAX_CITIES; i++) {\n        if (!visited&#91;i]) {\n            int min = INT_MAX;\n            for (j = 0; j &lt; MAX_CITIES; j++) {\n                if (dist&#91;city]&#91;j] &lt; min &amp;&amp; !visited&#91;j]) {\n                    min = dist&#91;city]&#91;j];\n                }\n            }\n            lb += min;\n        }\n    }\n\n    return lb;\n}\n\n\/\/ Function to find the minimum cost tour using Branch and Bound\nvoid tsp(int city, int level, int cost) {\n    if (level == MAX_CITIES) {\n        if (cost + dist&#91;city]&#91;0] &lt; min_cost) {\n            min_cost = cost + dist&#91;city]&#91;0]; \/\/ Calculate total cost including return to starting city\n        }\n        return;\n    }\n\n    for (int i = 0; i &lt; MAX_CITIES; i++) {\n        if (!visited&#91;i]) {\n            visited&#91;i] = 1;\n            tsp(i, level + 1, cost + dist&#91;city]&#91;i]);\n            visited&#91;i] = 0; \/\/ Backtrack\n        }\n    }\n}\n\nint main() {\n    int n;\n\n    \/\/ Get the number of cities\n    printf(\"Enter the number of cities: \");\n    scanf(\"%d\", &amp;n);\n\n    \/\/ Get the distance matrix\n    printf(\"Enter the distance matrix:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            scanf(\"%d\", &amp;dist&#91;i]&#91;j]);\n        }\n    }\n\n    \/\/ Initialize visited array\n    for (int i = 0; i &lt; n; i++) {\n        visited&#91;i] = 0;\n    }\n\n    visited&#91;0] = 1; \/\/ Start from city 0\n    tsp(0, 1, 0);\n\n    printf(\"Minimum cost of the tour: %d\\n\", min_cost);\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>dist[MAX_CITIES][MAX_CITIES]<\/code>: A 2D array to store the distances between cities.<\/li>\n\n\n\n<li><code>visited[MAX_CITIES]<\/code>: An array to keep track of visited cities.<\/li>\n\n\n\n<li><code>min_cost<\/code>: A variable to store the minimum cost of the tour, initialized to infinity (<code>INT_MAX<\/code>).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong><code>lower_bound()<\/code> function:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Calculates a lower bound on the cost of the remaining tour from a given city.<\/li>\n\n\n\n<li>For each unvisited city, finds the minimum distance to any other unvisited city.<\/li>\n\n\n\n<li>Sums these minimum distances to get a lower bound on the remaining cost.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong><code>tsp()<\/code> function:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Implements the recursive Branch and Bound algorithm.<\/li>\n\n\n\n<li><code>city<\/code>: The current city being visited.<\/li>\n\n\n\n<li><code>level<\/code>: The current level in the search tree.<\/li>\n\n\n\n<li><code>cost<\/code>: The cost of the path traversed so far.<\/li>\n\n\n\n<li>If all cities have been visited (<code>level == MAX_CITIES<\/code>):\n<ul class=\"wp-block-list\">\n<li>Calculate the total cost by adding the distance from the current city back to the starting city.<\/li>\n\n\n\n<li>Update <code>min_cost<\/code> if the total cost is less than the current minimum.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Otherwise:\n<ul class=\"wp-block-list\">\n<li>Iterate through all unvisited cities:\n<ul class=\"wp-block-list\">\n<li>Mark the city as visited.<\/li>\n\n\n\n<li>Recursively call <code>tsp()<\/code> with the next city, increased level, and updated cost.<\/li>\n\n\n\n<li>Unmark the city (backtrack).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong><code>main()<\/code> function:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Reads the number of cities and the distance matrix from the user.<\/li>\n\n\n\n<li>Initializes the <code>visited<\/code> array.<\/li>\n\n\n\n<li>Calls the <code>tsp()<\/code> function to find the minimum cost tour, starting from city 0.<\/li>\n\n\n\n<li>Prints the minimum cost of the tour.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Enter the number of cities: 4\nEnter the distance matrix:\n0 10 15 20\n10 0 35 25\n15 35 0 30\n20 25 30 0\nMinimum cost of the tour: 80 <\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\"><strong>\/\/C++ CODE FOR TSP<\/strong><\/mark>\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;limits.h&gt;\n\nusing namespace std;\n\nconst int MAX_CITIES = 20;\n\nclass TSP {\nprivate:\n    vector&lt;vector&lt;int&gt;&gt; dist; \/\/ Matrix to store distances between cities\n    vector&lt;bool&gt; visited; \/\/ Array to keep track of visited cities\n    int n; \/\/ Number of cities\n    int min_cost; \/\/ Minimum cost of the tour\n\n    \/\/ Function to calculate the lower bound for a given path\n    int lower_bound(int city) {\n        int lb = 0;\n        for (int i = 0; i &lt; n; i++) {\n            if (!visited&#91;i]) {\n                int min = INT_MAX;\n                for (int j = 0; j &lt; n; j++) {\n                    if (dist&#91;city]&#91;j] &lt; min &amp;&amp; !visited&#91;j]) {\n                        min = dist&#91;city]&#91;j];\n                    }\n                }\n                lb += min;\n            }\n        }\n        return lb;\n    }\n\n    \/\/ Function to find the minimum cost tour using Branch and Bound\n    void tsp(int city, int level, int cost) {\n        if (level == n) {\n            if (cost + dist&#91;city]&#91;0] &lt; min_cost) {\n                min_cost = cost + dist&#91;city]&#91;0]; \/\/ Calculate total cost including return to starting city\n            }\n            return;\n        }\n\n        for (int i = 0; i &lt; n; i++) {\n            if (!visited&#91;i]) {\n                visited&#91;i] = true;\n                tsp(i, level + 1, cost + dist&#91;city]&#91;i]);\n                visited&#91;i] = false; \/\/ Backtrack\n            }\n        }\n    }\n\npublic:\n    TSP(int numCities) : n(numCities), dist(n, vector&lt;int&gt;(n)), visited(n, false), min_cost(INT_MAX) {}\n\n    void setDistances(const vector&lt;vector&lt;int&gt;&gt;&amp; distances) {\n        dist = distances;\n    }\n\n    void findMinCostTour() {\n        visited&#91;0] = true; \/\/ Start from city 0\n        tsp(0, 1, 0);\n    }\n\n    int getMinCost() const {\n        return min_cost;\n    }\n};\n\nint main() {\n    int n;\n\n    cout &lt;&lt; \"Enter the number of cities: \";\n    cin &gt;&gt; n;\n\n    vector&lt;vector&lt;int&gt;&gt; distances(n, vector&lt;int&gt;(n));\n\n    cout &lt;&lt; \"Enter the distance matrix:\\n\";\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            cin &gt;&gt; distances&#91;i]&#91;j];\n        }\n    }\n\n    TSP tspSolver(n);\n    tspSolver.setDistances(distances);\n    tspSolver.findMinCostTour();\n\n    cout &lt;&lt; \"Minimum cost of the tour: \" &lt;&lt; tspSolver.getMinCost() &lt;&lt; endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image is-resized size-large\" id=\"BBNQUEEN\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-07-at-23.41.56-722x1024.jpeg\" alt=\"\" style=\"width:997px;height:auto\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image is-resized size-large\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-2-716x1024.jpg\" alt=\"\" style=\"width:995px;height:auto\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/ C code for NQueen<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n#include &lt;stdbool.h&gt;\n\/\/ Function to print the chessboard with queens placed\nvoid printSolution(int board&#91;], int N) {\n    \/\/ Print the chessboard row by row\n    for (int i = 0; i &lt; N; i++) {\n        for (int j = 0; j &lt; N; j++) {\n            \/\/ If the queen is placed in this column, print 'Q'\n            if (board&#91;i] == j)\n                printf(\"Q \");\n            else\n                printf(\". \");  \/\/ Otherwise, print an empty space\n        }\n        printf(\"\\n\");\n    }\n    printf(\"\\n\");\n}\n\n\/\/ Function to check if a queen can be safely placed at position (row, col)\nbool isSafe(int board&#91;], int row, int col) {\n    for (int i = 0; i &lt; row; i++) {\n        \/\/ Check if there is a queen already in the same column\n        \/\/ or if the current position (row, col) is attacked diagonally\n        if (board&#91;i] == col || \n            board&#91;i] - i == col - row ||   \/\/ Check for left diagonal conflict\n            board&#91;i] + i == col + row) {   \/\/ Check for right diagonal conflict\n            return false;  \/\/ If any conflict, return false\n        }\n    }\n    return true;  \/\/ No conflicts, safe to place queen\n}\n\n\/\/ Backtracking function to solve the N-Queen problem\nbool solveNQueen(int board&#91;], int row, int N) {\n    \/\/ If all queens are placed, we have found a solution\n    if (row == N) {\n        printSolution(board, N);  \/\/ Print the solution\n        return true;  \/\/ Return true to indicate a solution is found\n    }\n\n    bool res = false;  \/\/ Variable to store if any solution is found\n\n    \/\/ Try placing a queen in all columns of the current row\n    for (int col = 0; col &lt; N; col++) {\n        \/\/ Check if it's safe to place the queen in column `col` of row `row`\n        if (isSafe(board, row, col)) {\n            board&#91;row] = col;  \/\/ Place the queen in the current position\n            \/\/ Recursively try to place queens in the next row\n            res = solveNQueen(board, row + 1, N) || res;\n            board&#91;row] = -1;  \/\/ Backtrack, remove the queen and try next column\n        }\n    }\n    return res;  \/\/ Return true if a solution is found, false otherwise\n}\n\n\/\/ Function to start the Branch and Bound method to solve the N-Queen problem\nvoid branchAndBoundNQueen(int N) {\n    \/\/ Dynamically allocate memory for the board (1D array to store column indices of queens)\n    int* board = (int*)malloc(N * sizeof(int));\n\n    \/\/ Initialize the board with no queens placed (-1 indicates unassigned column)\n    for (int i = 0; i &lt; N; i++) {\n        board&#91;i] = -1;  \/\/ All rows are initially empty\n    }\n\n    \/\/ Call the recursive backtracking function starting from the first row\n    if (!solveNQueen(board, 0, N)) {\n        \/\/ If no solution is found, print a message\n        printf(\"No solution exists\\n\");\n    }\n\n    \/\/ Free dynamically allocated memory to avoid memory leaks\n    free(board);\n}\n\nint main() {\n    int N;\n\n    \/\/ Prompt user to input the value of N for the N-Queen problem\n    printf(\"Enter the value of N for the N-Queen problem: \");\n    scanf(\"%d\", &amp;N);\n\n    \/\/ Ensure that N is greater than or equal to 4, as the problem has no solution for N &lt; 4\n    if (N &lt; 4) {\n        printf(\"No solution exists for N &lt; 4\\n\");\n        return 0;  \/\/ Exit the program early as there is no solution for N &lt; 4\n    }\n\n    \/\/ Start the Branch and Bound process to solve the N-Queen problem\n    branchAndBoundNQueen(N);\n\n    return 0;\n}\n\n<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image is-resized size-full\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Picture1.png\" alt=\"\" style=\"width:994px;height:auto\"\/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"Expl\"><strong>Branch and Bound method for NQUEEN, KNAPSACK and Job Assignment problems<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\ud835\udc01\ud835\udc2b\ud835\udc1a\ud835\udc27\ud835\udc1c\ud835\udc21 \ud835\udc1a\ud835\udc27\ud835\udc1d \ud835\udc01\ud835\udc28\ud835\udc2e\ud835\udc27\ud835\udc1d: \ud835\udfd2 \ud835\udc10\ud835\udc14\ud835\udc04\ud835\udc04\ud835\udc0d\ud835\udc12|| \ud835\udfce\/\ud835\udfcf \ud835\udc0a\ud835\udc27\ud835\udc1a\ud835\udc29\ud835\udc2c\ud835\udc1a\ud835\udc1c\ud835\udc24||\ud835\udc09\ud835\udc28\ud835\udc1b \ud835\udc00\ud835\udc2c\ud835\udc2c\ud835\udc22\ud835\udc20\ud835\udc27\ud835\udc26\ud835\udc1e\ud835\udc27\ud835\udc2d \ud835\udc0f\ud835\udc2b\ud835\udc28\ud835\udc1b\ud835\udc25\ud835\udc1e\ud835\udc26, \ud835\udc01\ud835\udc1a\ud835\udc1c\ud835\udc24\ud835\udc2d\ud835\udc2b\ud835\udc1a\ud835\udc1c\ud835\udc24\ud835\udc22\ud835\udc27\ud835\udc20 \ud835\udc2f\ud835\udc2c \ud835\udc01\ud835\udc2b\ud835\udc1a\ud835\udc27\ud835\udc1c\ud835\udc21 \ud835\udc1a\ud835\udc27\ud835\udc1d \ud835\udc1b\ud835\udc28\ud835\udc2e\ud835\udc27\ud835\udc1d.\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Nxl_JhPMK3k?start=7&#038;feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>A* algorithm is a LC-BB<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image is-resized size-full\"><img decoding=\"async\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB1.jpg\" alt=\"\" style=\"width:995px;height:auto\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB2.jpg\" alt=\"\" class=\"wp-image-436\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB2.jpg 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB2-300x225.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB2-768x576.jpg 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB3.jpg\" alt=\"\" class=\"wp-image-437\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB3.jpg 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB3-300x225.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB3-768x576.jpg 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR1.jpg\" alt=\"\" class=\"wp-image-431\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR1.jpg 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR1-300x225.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR1-768x576.jpg 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR2.jpg\" alt=\"\" class=\"wp-image-432\" style=\"width:1199px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR2.jpg 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR2-300x225.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR2-768x576.jpg 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR3.jpg\" alt=\"\" class=\"wp-image-433\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR3.jpg 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR3-300x225.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/LCBB_A_STAR3-768x576.jpg 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>Job Sequencing with Deadlines using Branch and Bound. How does FIFO BB work for job sequencing with deadlines, penalties, and execution time? Solving 0-1 Knapsack using Branch and Bound Branch and bound for Travelling Sales Person (TSP) problem The travelling salesperson problem, also known as travelling salesman problem (TSP), asks the following question: &#8220;Given a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-377","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/377","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=377"}],"version-history":[{"count":35,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/377\/revisions"}],"predecessor-version":[{"id":1768,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/377\/revisions\/1768"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=377"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}