DSA CODES
1 BST
2 BFS DFS
3 NON LINEAR DATA STRUCTURE/ MAX HEAP/ INTERNSHIP/ SORT STUDENT GRADE
4 DIVIDE AND CONQUER
5 PRIMS AND KRUSHKALS ALGO
6 DIJKISTRAS ALGO/ BELLMON FOR
7 GRAPH COLORING / N QUEENS
8 BRANCH N BOUND FOR TSP N KNAPSACK 0/1
1. Aim: Create a binary search tree (BST) of and perform following operations: i) Insert ii)Display inorder iii)Search a node iv) Find height of the tree v) level wise display iv)
Delete v) Mirror
Code:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int val) : data(val),
left(nullptr), right(nullptr) {}
};
Node* insert(Node* root, int value)
{
if (root == nullptr)
{
return new Node(value);
}
if (value < root->data)
{
root->left = insert(root->left,
value);
}
else
{
root->right = insert(root->right,
value);
}
return root;
}
void inorderTraversal(Node*
root)
{
if (root != nullptr)
{
inorderTraversal(root->left);
cout << root->data <<
" ";
inorderTraversal(root->right);
}
}
Node*
search(Node* root, int value)
{
if (root == nullptr || root->data ==
value)
{
return root;
}
if (value < root->data)
{
return search(root->left, value);
}
return search(root->right, value);
}
int
height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return max(leftHeight, rightHeight) + 1;
}
Node*
deleteNode(Node* root, int value)
{
if (root == nullptr)
{
return root;
}
if (value < root->data)
{
root->left =
deleteNode(root->left, value);
}
else if (value > root->data)
{
root->right =
deleteNode(root->right, value);
}
else
{
if (root->left == nullptr)
{
Node* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr)
{
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = root->right;
while (temp && temp->left !=
nullptr)
{
temp = temp->left;
}
root->data = temp->data;
root->right =
deleteNode(root->right, temp->data);
}
return root;
}
void
mirrorImage(Node* root)
{
if (root == nullptr)
{
return;
}
Node* temp = root->left;
root->left = root->right;
root->right = temp;
mirrorImage(root->left);
mirrorImage(root->right);
}
int main()
{
Node* root = nullptr;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
cout << "Inorder Traversal:
";
inorderTraversal(root);
cout << endl;
int searchVal = 40;
Node* searchResult = search(root,
searchVal);
if (searchResult)
{
cout << "Node "
<< searchVal << " found!" << endl;
} else
{
cout << "Node "
<< searchVal << " not found!" << endl;
}
cout << "Height of tree: "
<< height(root) << endl;
cout << "Tree (Inorder
Traversal): ";
inorderTraversal(root);
cout << endl;
int deleteVal = 20;
root = deleteNode(root, deleteVal);
cout << "Tree after deleting
node " << deleteVal << ": ";
inorderTraversal(root);
cout << endl;
mirrorImage(root);
cout << "Tree after creating
mirror image (Inorder Traversal): ";
inorderTraversal(root);
cout << endl;
return 0;
}
Output:
2 Aim: Create a graph and perform graph traversal using BFS and DFS.
Code:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph{
int V;
vector<vector<int>> adjList;
public:
Graph(int V)
{
this->V = V;
adjList.resize(V);
}
void addEdge(int v, int w)
{
adjList[v].push_back(w);
adjList[w].push_back(v);
}
void BFS(int start)
{
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
cout << "BFS Traversal starting from vertex " <<
start << ": ";
while (!q.empty())
{
int node = q.front();
cout << node << " ";
q.pop();
for (auto neighbor : adjList[node])
{
if (!visited[neighbor])
{
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
void
DFSUtil(int node, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (auto neighbor : adjList[node])
{
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}
void
DFS(int start){
vector<bool> visited(V, false);
cout << "DFS Traversal starting from vertex " <<
start << ": ";
DFSUtil(start, visited);
cout << endl;
}
};
int main()
{
int
V = 6;
Graph g(V);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
g.BFS(0);
g.DFS(0);
return 0;
}
Output:
3 Aim: a)
The internship is offered to students based on rank obtained in the second year
of
graduation. Create a suitable
non-linear data structure to identify the next topper
student for internship. (Create
max-heap).
b) Sort the student data in
ascending order of grades
Code:
#include <iostream>
#include
<vector>
#include
<limits>
#include
<algorithm>
#include
<sstream>
using
namespace std;
struct
Student
{
int roll_no;
string name;
int grade;
};
void
max_heapify(vector<Student>& students, int i, int n)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n &&
students[left].grade > students[largest].grade)
largest = left;
if (right < n &&
students[right].grade > students[largest].grade)
largest = right;
if (largest != i)
{
swap(students[i], students[largest]);
max_heapify(students, largest, n);
}
}
void
build_max_heap(vector<Student>& students, int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
max_heapify(students, i, n);
}
void
heap_sort(vector<Student>& students, int n)
{
build_max_heap(students, n);
for (int i = n - 1; i > 0; i--)
{
swap(students[0], students[i]);
max_heapify(students, 0, i);
}
}
void
display_students(const vector<Student>& students)
{
for (const auto& student : students)
{
cout << "Roll No: "
<< student.roll_no
<< ", Name: "
<< student.name
<< ", Grade: "
<< student.grade << endl;
}
}
int main()
{
int n;
cout << "Enter the number of
students: ";
cin >> n;
vector<Student> students(n);
cout << "Enter student details
(Roll No, Name, Grade):" << endl;
cin.ignore();
for (int i = 0; i < n; i++)
{
string line;
getline(cin, line);
istringstream iss(line);
iss >> students[i].roll_no;
string temp;
iss >> temp;
students[i].name = temp;
while (iss >> temp &&
isalpha(temp[0]))
{
students[i].name += " " +
temp;
}
students[i].grade = temp[0] - 'A';
}
build_max_heap(students, n);
cout << "\nTopper for internship
(Max-Heap Root): Roll No: "
<< students[0].roll_no <<
", Name: " << students[0].name
<< ", Grade: "
<< students[0].grade << endl;
heap_sort(students, n);
reverse(students.begin(), students.end());
cout << "\nSorted students by
grade in ascending order:\n";
display_students(students);
return 0;
}
Output:
4 Aim: Divide and Conquer: Implement a program to find minimum and
maximum elements from a given list using Divide and Conquer strategy.
Code:
#include <iostream>
using namespace std;
void merge(int arr[], int left, int
mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArr[n1], rightArr[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (leftArr[i] <= rightArr[j])
{
arr[k] = leftArr[i];
i++;
}
else
{
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = rightArr[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left,
int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << "
";
cout << endl;
}
int main()
{
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: ";
printArray(arr, size);
return 0;
}
Output:
5 Aim: A
business house has several offices in different countries; they want to lease
phone lines to connect them with each other and the phone company charges
different rent to connect different pairs of cities. Business house wants to
connect all its offices with a minimum total cost. Represent using appropriate
data structure. Apply Prim’s and Kruskal’s algorithm to find the minimum total
cost.
Code:
#include <iostream>
#include
<vector>
#include
<algorithm>
#include
<climits>
using
namespace std;
struct Edge
{
int src, dest, weight;
};
bool
compareEdge(Edge a, Edge b)
{
return a.weight < b.weight;
}
class Graph
{
int V;
vector<vector<pair<int,
int>>> adjList;
vector<Edge> edges;
public:
Graph(int V)
{
this->V = V;
adjList.resize(V);
}
void addEdge(int src, int dest, int weight)
{
adjList[src].push_back({dest, weight});
adjList[dest].push_back({src, weight});
edges.push_back({src, dest, weight});
}
void primMST()
{
vector<int> key(V, INT_MAX);
vector<bool> inMST(V, false);
vector<int> parent(V, -1);
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1;
count++)
{
int u = -1;
for (int i = 0; i < V; i++)
if (!inMST[i] && (u ==
-1 || key[i] < key[u]))
u = i;
inMST[u] = true;
for (auto [v, weight] : adjList[u])
{
if (!inMST[v] && weight
< key[v])
{
key[v] = weight;
parent[v] = u;
}
}
}
cout << "\nMinimum Spanning
Tree using Prim's Algorithm:\n";
int totalCost = 0;
for (int i = 1; i < V; i++)
{
cout << parent[i] <<
" - " << i << " (Cost: " << key[i]
<< ")\n";
totalCost += key[i];
}
cout << "Total Minimum Cost:
" << totalCost << endl;
}
int findSet(int parent[], int i)
{
if (parent[i] == i)
return i;
return parent[i] = findSet(parent,
parent[i]);
}
void unionSets(int parent[], int rank[],
int u, int v)
{
u = findSet(parent, u);
v = findSet(parent, v);
if (rank[u] < rank[v])
parent[u] = v;
else if (rank[u] > rank[v])
parent[v] = u;
else
{
parent[v] = u;
rank[u]++;
}
}
void kruskalMST()
{
sort(edges.begin(), edges.end(),
compareEdge);
vector<Edge> mst;
int parent[V], rank[V];
for (int i = 0; i < V; i++)
{
parent[i] = i;
rank[i] = 0;
}
int totalCost = 0;
for (auto edge : edges)
{
int u = findSet(parent, edge.src);
int v = findSet(parent, edge.dest);
if (u != v)
{
mst.push_back(edge);
totalCost += edge.weight;
unionSets(parent, rank, u, v);
}
}
cout << "\nMinimum Spanning
Tree using Kruskal's Algorithm:\n";
for (auto edge : mst)
{
cout << edge.src <<
" - " << edge.dest << " (Cost: " <<
edge.weight << ")\n";
}
cout << "Total Minimum Cost:
" << totalCost << endl;
}
};
int main()
{
int V, E;
cout << "Enter the number of
offices (nodes): ";
cin >> V;
cout << "Enter the number of
connections (edges): ";
cin >> E;
Graph g(V);
cout << "Enter the edges (src
dest cost):\n";
for (int i = 0; i < E; i++)
{
int u, v, weight;
cin >> u >> v >>
weight;
g.addEdge(u, v, weight);
}
g.primMST();
g.kruskalMST();
return 0;
}
Output:
6 Aim: a) Use the map of the area around the college as the graph.
Identify the prominent landmarks as nodes and find minimum distance to various
landmarks from the college as the source. Represent this graph using an
adjacency matrix. Find the
shortest path using Dijkstra’s
algorithm.
Code: a)Shortest Path using
Dijkstra’s Algorithm
#include
<iostream>
#include <vector>
#include <climits>
using namespace std;
#define V 5
int minDistance(const
vector<int>& dist, const vector<bool>& visited) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v]
<= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
void dijkstra(int graph[V][V], int
src)
{
vector<int> dist(V, INT_MAX);
vector<bool> visited(V, false);
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = minDistance(dist,
visited);
visited[u] = true;
for (int v = 0; v < V; v++)
if (!visited[v] &&
graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] <
dist[v])
dist[v] = dist[u] +
graph[u][v];
}
cout << "Shortest distances from the college (node "
<< src << ") to other landmarks:\n";
for (int i = 0; i < V; i++)
cout << "Node "
<< i << " -> Distance: " << dist[i] <<
endl;
}
int main()
{
int graph[V][V] =
{
{0, 10, 0, 5, 0},
{10, 0, 1, 2, 0},
{0, 1, 0, 9, 3},
{5, 2, 9, 0, 2},
{0, 0, 3, 2, 0}
};
dijkstra(graph, 0);
return 0;
}
Output: a) Shortest Path using Dijkstra’s Algorithm
b) Write a program to implement the Bellman-Ford algorithm to find the shortest
path from a single source to all other nodes in a graph with negative edge weights.
Verify its results for a sample graph and compare it with Dijkstra’s algorithm.
Code: b) Shortest Path using Bellman-Ford
Algorithm
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Edge
{
int src, dest, weight;
};
void
bellmanFord(vector<Edge>& edges, int V, int src)
{
vector<int> dist(V, INT_MAX);
dist[src] = 0;
for (int i = 0; i < V - 1; i++)
{
for (const auto& edge : edges)
{
if (dist[edge.src] != INT_MAX
&& dist[edge.src] + edge.weight < dist[edge.dest])
dist[edge.dest] =
dist[edge.src] + edge.weight;
}
}
for (const auto& edge : edges)
{
if (dist[edge.src] != INT_MAX
&& dist[edge.src] + edge.weight < dist[edge.dest])
{
cout << "Graph contains
a negative weight cycle!\n";
return;
}
}
cout << "\nShortest distances from node " << src
<< " using Bellman-Ford Algorithm:\n";
for (int i = 0; i < V; i++)
cout << "Node "
<< i << " -> Distance: " << dist[i] <<
endl;
}
int main()
{
int V = 5;
int E = 8;
vector<Edge> edges =
{
{0, 1, -1}, {0, 2, 4},
{1, 2, 3}, {1, 3, 2}, {1, 4, 2},
{3, 2, 5}, {3, 1, 1}, {4, 3, -3}
};
bellmanFord(edges, V, 0);
return 0;
}
Output: b) Shortest Path using Bellman-Ford Algorithm
Aim: a) Use the map of the area around the college as the graph.
Identify the prominent landmarks as nodes and find
distance to various landmarks from the college as the source.
Represent this graph using an adjacency matrix. Find the
shortest path using Dijkstra’s
algorithm.
Code: a)Shortest Path using
Dijkstra’s Algorithm
#include
<iostream>
#include <vector>
#include <climits>
using namespace std;
#define V 5
int minDistance(const
vector<int>& dist, const vector<bool>& visited) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v]
<= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
void dijkstra(int graph[V][V], int
src)
{
vector<int> dist(V, INT_MAX);
vector<bool> visited(V, false);
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = minDistance(dist,
visited);
visited[u] = true;
for (int v = 0; v < V; v++)
if (!visited[v] &&
graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] <
dist[v])
dist[v] = dist[u] +
graph[u][v];
}
cout << "Shortest distances from the college (node "
<< src << ") to other landmarks:\n";
for (int i = 0; i < V; i++)
cout << "Node "
<< i << " -> Distance: " << dist[i] <<
endl;
}
int main()
{
int graph[V][V] =
{
{0, 10, 0, 5, 0},
{10, 0, 1, 2, 0},
{0, 1, 0, 9, 3},
{5, 2, 9, 0, 2},
{0, 0, 3, 2, 0}
};
dijkstra(graph, 0);
return 0;
}
Output: a) Shortest Path using Dijkstra’s Algorithm
b) Write a program to implement the Bellman-Ford algorithm to find the shortest
path from a single source to all other nodes in a graph with negative edge weights.
Verify its results for a sample graph and compare it with Dijkstra’s algorithm.
Code: b) Shortest Path using Bellman-Ford
Algorithm
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Edge
{
int src, dest, weight;
};
void
bellmanFord(vector<Edge>& edges, int V, int src)
{
vector<int> dist(V, INT_MAX);
dist[src] = 0;
for (int i = 0; i < V - 1; i++)
{
for (const auto& edge : edges)
{
if (dist[edge.src] != INT_MAX
&& dist[edge.src] + edge.weight < dist[edge.dest])
dist[edge.dest] =
dist[edge.src] + edge.weight;
}
}
for (const auto& edge : edges)
{
if (dist[edge.src] != INT_MAX
&& dist[edge.src] + edge.weight < dist[edge.dest])
{
cout << "Graph contains
a negative weight cycle!\n";
return;
}
}
cout << "\nShortest distances from node " << src
<< " using Bellman-Ford Algorithm:\n";
for (int i = 0; i < V; i++)
cout << "Node "
<< i << " -> Distance: " << dist[i] <<
endl;
}
int main()
{
int V = 5;
int E = 8;
vector<Edge> edges =
{
{0, 1, -1}, {0, 2, 4},
{1, 2, 3}, {1, 3, 2}, {1, 4, 2},
{3, 2, 5}, {3, 1, 1}, {4, 3, -3}
};
bellmanFord(edges, V, 0);
return 0;
}
7 Aim: Backtracking:
a) Solve Graph Coloring problem
using backtracking approaches.
Code: a) Graph
Coloring problem using backtracking approaches.
#include <iostream>
#include <vector>
using namespace std;
bool isSafe(int node,
vector<vector<int>>& graph, vector<int>& color, int
c, int n)
{
for (int i = 0; i < n; i++)
{
if (graph[node][i] == 1 &&
color[i] == c)
return false;
}
return true;
}
bool solve(int node,
vector<vector<int>>& graph, vector<int>& color, int
m, int n)
{
if (node == n)
return true;
for (int c = 1; c <= m; c++)
{
if (isSafe(node, graph, color, c, n))
{
color[node] = c;
if (solve(node + 1, graph, color,
m, n))
return true;
color[node] = 0;
}
}
return false;
}
int main()
{
int n, m;
cout << "Enter number of vertices: ";
cin >> n;
cout << "Enter number of colors: ";
cin >> m;
vector<vector<int>> graph(n, vector<int>(n));
cout << "Enter adjacency matrix:\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> graph[i][j];
vector<int> color(n, 0);
if (solve(0, graph, color, m, n))
{
cout << "Color
assignment:\n";
for (int i = 0; i < n; i++)
cout << "Vertex "
<< i << " ---> Color " << color[i] <<
endl;
}
else
{
cout << "No solution exists
with " << m << " colors.\n";
}
return 0;
}
Output:
e: b)
N-Queens Problem
queens on a chess board so that no queen takes each other.
#include <iostream>
#include <vector>
using namespace std;
bool
isSafe(vector<vector<int>>& board, int row, int col, int rows,
int cols)
{
for (int i = 0; i < row; i++)
if (board[i][col] == 1)
return false;
for (int j = 0; j < col; j++)
if (board[row][j] == 1)
return false;
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,
j--)
if (board[i][j] == 1)
return false;
for (int i = row - 1, j = col + 1; i >= 0 && j < cols;
i--, j++)
if (board[i][j] == 1)
return false;
for (int i = row + 1, j = col - 1; i < rows && j >= 0;
i++, j--)
if (board[i][j] == 1)
return false;
for (int i = row + 1, j = col + 1; i < rows && j < cols;
i++, j++)
if (board[i][j] == 1)
return false;
for (int i = row + 1; i < rows; i++)
if (board[i][col] == 1)
return false;
for (int j = col + 1; j < cols; j++)
if (board[row][j] == 1)
return false;
return true;
}
bool
placeQueens(vector<vector<int>>& board, int rows, int cols, int
queensToPlace, int startRow = 0)
{
if (queensToPlace == 0)
return true;
for (int i = startRow; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (isSafe(board, i, j, rows,
cols))
{
board[i][j] = 1;
if (placeQueens(board, rows,
cols, queensToPlace - 1, i))
return true;
board[i][j] = 0;
}
}
}
return false;
}
void printBoard(const
vector<vector<int>>& board, int rows, int cols) {
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
cout << (board[i][j] == 1 ?
"Q " : ". ");
cout << endl;
}
}
int main()
{
int rows, cols, queens;
cout << "Enter number of rows: ";
cin >> rows;
cout << "Enter number of columns: ";
cin >> cols;
cout << "Enter number of queens to place: ";
cin >> queens;
if (queens > rows * cols)
{
cout << "Too many queens for
the board size!" << endl;
return 0;
}
vector<vector<int>> board(rows, vector<int>(cols, 0));
if (placeQueens(board, rows, cols, queens))
{
cout <<
"\nSolution:\n";
printBoard(board, rows, cols);
}
else
{
cout << "No solution
possible for given input.\n";
}
return 0;
}
OUTPUT:
Aim: Branch and Bound:
a)Write a program to solve the travelling salesman problem. Print the path and the cost.
Code: a) Write a
program to solve the travelling salesman problem. Print the path and the cost.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int
tsp(vector<vector<int>>& graph, vector<bool>&
visited, int pos, int n, int count, int cost, int start, vector<int>&
path, vector<int>& bestPath, int& minCost)
{
if (count == n && graph[pos][start])
{
cost += graph[pos][start];
if (cost < minCost)
{
minCost = cost;
bestPath = path;
bestPath.push_back(start);
}
return cost;
}
for (int i = 0; i < n; i++)
{
if (!visited[i] &&
graph[pos][i])
{
visited[i] = true;
path.push_back(i);
tsp(graph, visited, i, n, count +
1, cost + graph[pos][i], start, path, bestPath, minCost);
visited[i] = false;
path.pop_back();
}
}
return minCost;
}
int main()
{
int n;
cout << "Enter number of cities: ";
cin >> n;
vector<vector<int>> graph(n, vector<int>(n));
cout << "Enter cost matrix:\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> graph[i][j];
vector<bool> visited(n, false);
vector<int> path, bestPath;
int minCost = INT_MAX;
int start = 0;
visited[start] = true;
path.push_back(start);
tsp(graph, visited, start, n, 1, 0, start, path, bestPath, minCost);
cout << "\nMinimum Cost: " << minCost <<
endl;
cout << "Path: ";
for (int city : bestPath)
cout << city << "
";
cout << endl;
return 0;
}
Output:
b) B Implement branch and bound for the 0/1 Knapsack problem.
b) Implement
branch and bound for the 0/1 Knapsack problem
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Item
{
int weight, value;
double ratio;
};
bool cmp(Item a, Item b)
{
return a.ratio > b.ratio;
}
struct Node
{
int level, profit, weight;
double bound;
};
double bound(Node u, int n, int W,
vector<Item>& items)
{
if (u.weight >= W) return 0;
double profit_bound = u.profit;
int j = u.level + 1;
int totweight = u.weight;
while ((j < n) && (totweight + items[j].weight <= W))
{
totweight += items[j].weight;
profit_bound += items[j].value;
j++;
}
if (j < n)
profit_bound += (W - totweight) *
items[j].ratio;
return profit_bound;
}
int knapsack(int W,
vector<Item>& items, int n)
{
sort(items.begin(), items.end(), cmp);
queue<Node> Q;
Node u, v;
u.level = -1;
u.profit = u.weight = 0;
u.bound = bound(u, n, W, items);
Q.push(u);
int maxProfit = 0;
while (!Q.empty())
{
u = Q.front();
Q.pop();
if (u.level == n - 1)
continue;
v.level = u.level + 1;
v.weight = u.weight +
items[v.level].weight;
v.profit = u.profit +
items[v.level].value;
if (v.weight <= W &&
v.profit > maxProfit)
maxProfit = v.profit;
v.bound = bound(v, n, W, items);
if (v.bound > maxProfit)
Q.push(v);
v.weight = u.weight;
v.profit = u.profit;
v.bound = bound(v, n, W, items);
if (v.bound > maxProfit)
Q.push(v);
}
return maxProfit;
}
int main()
{
int n, W;
cout << "Enter number of items: ";
cin >> n;
vector<Item> items(n);
cout << "Enter weights and values of items:\n";
for (int i = 0; i < n; i++)
{
cin >> items[i].weight >>
items[i].value;
items[i].ratio = (double)items[i].value
/ items[i].weight;
}
cout << "Enter maximum capacity of knapsack: ";
cin >> W;
int maxProfit = knapsack(W, items, n);
cout << "Maximum Profit: " << maxProfit <<
endl;
return 0;
}
OUTPUT:
Comments
Post a Comment