Program: 07
Object:Write a c program to implementation of Knapsack Problem using Greedy
Solution
#include <stdio.h>
struct Item {
int value;
int weight;
double ratio;
};
void swap(struct Item items[], int i, int j) {
struct Item temp = items[i];
items[i] = items[j];
items[j] = temp;
}
void sortItemsByRatio(struct Item items[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (items[j].ratio < items[j + 1].ratio) {
swap(items, j, j + 1);
}
}
}
}
double knapsack(int capacity, struct Item items[], int size) {
sortItemsByRatio(items, size);
double totalValue = 0.0;
for (int i = 0; i < size; i++) {
if (capacity >= items[i].weight) {
capacity -= items[i].weight;
totalValue += items[i].value;
} else {
totalValue += items[i].value * ((double)capacity / items[i].weight);
break;
}
}
return totalValue;
}
int main() {
int n, capacity;
printf("Enter the number of items: ");
scanf("%d", &n);
struct Item items[n];
for (int i = 0; i < n; i++) {
printf("Enter value and weight of item %d: ", i + 1);
scanf("%d %d", &items[i].value, &items[i].weight);
items[i].ratio = (double)items[i].value / items[i].weight;
}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
double maxValue = knapsack(capacity, items, n);
printf("Maximum value in knapsack = %.2f\n", maxValue);
return 0;
}
Output:
Enter the number of items: 3
Enter value and weight of item 1: 40 20
Enter value and weight of item 2: 20 10
Enter value and weight of item 3: 120 40
Enter the capacity of the knapsack: 100
Maximum value in knapsack = 180.00
Program: 08
Object: Write a c program to implementation of Travelling Salesman Problem
#include <stdio.h>
#define MAX 10
#define INF 9999
int graph[MAX][MAX];
int n;
int min(int a, int b) {
return (a < b) ? a : b;
}
int tsp(int currentCity, int visitedCities, int pathLength, int startCity) {
if (visitedCities == (1 << n) - 1) {
return pathLength + graph[currentCity][startCity];
}
int minCost = INF;
for (int i = 0; i < n; i++) {
if ((visitedCities & (1 << i)) == 0) {
minCost = min(minCost, tsp(i, visitedCities | (1 << i), pathLength + graph[currentCity][i],
startCity));
}
}
return minCost;
}
int main() {
printf("Enter the number of cities: ");
scanf("%d", &n);
printf("Enter the distance matrix (use 0 for no direct path):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
if (graph[i][j] == 0 && i != j) {
graph[i][j] = INF; // Use a large number to represent no direct path
}
}
}
int minCost = tsp(0, 1, 0, 0);
printf("Minimum cost to visit all cities = %d\n", minCost);
return 0;
}
Output:
Enter the number of cities: 5
Enter the distance matrix (use 0 for no direct path):
10 15 20 40 20
10 30 59 20 39
11 23 24 54 34
45 43 35 43 54
43 89 57 45 42
Minimum cost to visit all cities = 133
Program: 09
Object: Write a c program to Find Minimum Spanning Tree using Kruskal’s
Algorithm.
#include <stdio.h>
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge edge[100];
};
struct Subset {
int parent;
int rank;
};
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
void sortEdges(struct Graph* graph) {
for (int i = 0; i < graph->E - 1; i++) {
for (int j = 0; j < graph->E - i - 1; j++) {
if (graph->edge[j].weight > graph->edge[j + 1].weight) {
struct Edge temp = graph->edge[j];
graph->edge[j] = graph->edge[j + 1];
graph->edge[j + 1] = temp;
}
}
}
}
void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[100];
int e = 0;
int i = 0;
sortEdges(graph);
struct Subset subsets[V];
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
int minCost = 0;
while (e < V - 1 && i < graph->E) {
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
minCost += next_edge.weight;
Union(subsets, x, y);
}
}
printf("Edges in the Minimum Spanning Tree:\n");
for (i = 0; i < e; ++i)
printf("%d -- %d == %d\n", result[i].src + 1, result[i].dest + 1, result[i].weight);
printf("Minimum cost of the spanning tree: %d\n", minCost);
}
int main() {
struct Graph graph;
printf("Enter the number of vertices: ");
scanf("%d", &graph.V);
printf("Enter the number of edges: ");
scanf("%d", &graph.E);
for (int i = 0; i < graph.E; i++) {
printf("Enter source, destination, and weight of edge %d: ", i + 1);
scanf("%d %d %d", &[Link][i].src, &[Link][i].dest, &[Link][i].weight);
[Link][i].src--; // Adjust index to 0-based
[Link][i].dest--; // Adjust index to 0-based
}
KruskalMST(&graph);
return 0;
}
Output
Enter the number of vertices: 3
Enter the number of edges: 3
Enter source, destination, and weight of edge 1: 0 1 5
Enter source, destination, and weight of edge 2: 1 2 3
Enter source, destination, and weight of edge 3: 0 2 1
Edges in the Minimum Spanning Tree:
0 -- 2 == 1
1 -- 2 == 3
Minimum cost of the spanning tree: 4
Program: 10
Object: Write a c program to Implement N Queen Problem using Backtracking
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 20
int totalSolutions = 0;
void printSolution(int N, int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 1)
printf("Q ");
else
printf("* ");
}
printf("\n");
}
printf("\n");
}
bool isSafe(int N, int board[N][N], int row, int col) {
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(int N, int board[N][N], int col) {
if (col >= N) {
printSolution(N, board);
totalSolutions++;
return true;
}
for (int i = 0; i < N; i++) {
if (isSafe(N, board, i, col)) {
board[i][col] = 1;
solveNQUtil(N, board, col + 1);
board[i][col] = 0;
}
}
return false;
}
void solveNQ(int N) {
int board[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
board[i][j] = 0;
totalSolutions = 0;
solveNQUtil(N, board, 0);
printf("Total solutions: %d\n", totalSolutions);
}
int main() {
int N;
printf("Enter the size of the chessboard (N): ");
scanf("%d", &N);
if (N > MAX_N) {
printf("N is too large! Please use a value less than or equal to %d.\n", MAX_N);
return 1;
}
solveNQ(N);
return 0;
}
Output:
Enter the size of the chessboard (N): 4
**Q*
Q***
***Q
*Q**
*Q**
***Q
Q***
**Q*
Total solutions: 2
Program: 11
Object: Write a c program to Implement , the 0/1 Knapsack problem using
Dynamic Programming method.
#include <stdio.h>
int knapsack(int W, int weights[], int values[], int n) {
int dp[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (weights[i - 1] <= w) {
dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]] > dp[i - 1][w])
? values[i - 1] + dp[i - 1][w - weights[i - 1]]
: dp[i - 1][w];
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
int main() {
int n, W;
printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the maximum weight of the knapsack: ");
scanf("%d", &W);
int weights[n], values[n];
printf("Enter the weights of the items:\n");
for (int i = 0; i < n; i++) {
printf("Weight of item %d: ", i + 1);
scanf("%d", &weights[i]);
}
printf("Enter the values of the items:\n");
for (int i = 0; i < n; i++) {
printf("Value of item %d: ", i + 1);
scanf("%d", &values[i]);
}
int max_value = knapsack(W, weights, values, n);
printf("The maximum value that can be obtained is: %d\n", max_value);
return 0;
}
Output:
Enter the number of items: 4
Enter the maximum weight of the knapsack: 100
Enter the weights of the items:
Weight of item 1: 30
Weight of item 2: 40
Weight of item 3: 50
Weight of item 4: 30
Enter the values of the items:
Value of item 1: 50
Value of item 2: 60
Value of item 3: 80
Value of item 4: 120
The maximum value that can be obtained is: 230
Program: 12
Object: Write a c program to implement to find all Hamiltonian Cycles in a
connected undirected Graph G of n vertices using backtracking principle.
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 20
void printCycle(int path[], int n) {
for (int i = 0; i < n; i++)
printf("%d -> ", path[i]);
printf("%d\n", path[0]);
bool isSafe(int graph[MAX_VERTICES][MAX_VERTICES], int path[], int pos, int v, int n) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
bool hamCycleUtil(int graph[MAX_VERTICES][MAX_VERTICES], int path[], int pos, int n) {
if (pos == n) {
if (graph[path[pos - 1]][path[0]] == 1)
return true;
return false;
}
for (int v = 1; v < n; v++) {
if (isSafe(graph, path, pos, v, n)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1, n))
return true;
path[pos] = -1;
}
}
return false;
}
void findHamiltonianCycles(int graph[MAX_VERTICES][MAX_VERTICES], int n) {
int path[MAX_VERTICES];
for (int i = 0; i < n; i++)
path[i] = -1;
path[0] = 0;
if (!hamCycleUtil(graph, path, 1, n)) {
printf("No Hamiltonian Cycle exists\n");
} else {
printf("Hamiltonian Cycle found:\n");
printCycle(path, n);
}
}
int main() {
int n;
int graph[MAX_VERTICES][MAX_VERTICES];
printf("Enter the number of vertices: ");
scanf("%d", &n);
if (n > MAX_VERTICES) {
printf("Number of vertices exceeds the maximum allowed value (%d).\n",
MAX_VERTICES);
return 1;
}
printf("Enter the adjacency matrix (enter 1 for an edge and 0 for no edge):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
findHamiltonianCycles(graph, n);
return 0;
}
Output:
Enter the number of vertices: 5
Enter the adjacency matrix (enter 1 for an edge and 0 for no edge):
01010
10111
01001
11001
01110
Hamiltonian Cycle found:
0 -> 1 -> 2 -> 4 -> 3 -> 0