12. N Queens

 #include<stdio.h>

#include<math.h>

#include<stdlib.h>

int board[20],count;

 

int main()

{

int n,i,j;

void queen(int row,int n);

 

printf(" - N Queens Problem Using Backtracking -");

printf("\n\nEnter number of Queens:");

scanf("%d",&n);

queen(1,n);

return 0;

}

 

void print(int n)

{

int i,j;

printf("\n\nSolution %d:\n\n",++count);

 

for(i=1;i<=n;++i)

  printf("\t%d",i);

 

for(i=1;i<=n;++i)

{

  printf("\n\n%d",i);

  for(j=1;j<=n;++j)

  {

   if(board[i]==j)

    printf("\tQ");

   else

    printf("\t-");

  }

}

}

 

int place(int row,int column)

{

int i;

for(i=1;i<=row-1;++i)

{

  if(board[i]==column)

   return 0;

  else

   if(abs(board[i]-column)==abs(i-row))

    return 0;

}

 

return 1;

}

 

void queen(int row,int n)

{

int column;

for(column=1;column<=n;++column)

{

  if(place(row,column))

  {

   board[row]=column;

   if(row==n)

    print(n);

   else

    queen(row+1,n);

  }

}

}

OUTPUT:

no of queens:4

8. subset of a given set

 #include <stdio.h>

#include <stdbool.h>

#define MAX_SIZE 100

// Function to find subset with given sum

void subsetSum(int set[], int subset[], int n, int subSize, int total, int nodeCount, int sum) {

    if (total == sum) {

        // Print the subset

        printf("Subset found: { ");

        for (int i = 0; i < subSize; i++) {

            printf("%d ", subset[i]);

        }

        printf("}\n");

        return;

    } else {

        // Check the sum of the remaining elements

        for (int i = nodeCount; i < n; i++) {

            subset[subSize] = set[i];

            subsetSum(set, subset, n, subSize + 1, total + set[i], i + 1, sum);

        }

    }

}

int main() {

    int set[MAX_SIZE];

    int subset[MAX_SIZE];

    int n, sum;

    // Input the number of elements in the set

    printf("Enter the number of elements in the set: ");

    scanf("%d", &n);

    // Input the elements of the set

    printf("Enter the elements of the set:\n");

    for (int i = 0; i < n; i++) {

        scanf("%d", &set[i]);

    }

    // Input the target sum

    printf("Enter the sum to find subset for: ");

    scanf("%d", &sum);

    printf("Subsets with sum %d:\n", sum);

    subsetSum(set, subset, n, 0, 0, 0, sum);

    return 0;

}

OUTPUT:

no of ele: 5

eles:

2

4

6

8

10

sum:10

7. greedy approximation method

 #include <stdio.h>

#include <stdlib.h>

struct Item {

    int value;

    int weight;

    double ratio; /

};

int compare(const void *a, const void *b) {

    struct Item *item1 = (struct Item *)a;

    struct Item *item2 = (struct Item *)b;

    double ratio1 = item1->ratio;

    double ratio2 = item2->ratio;

    if (ratio1 > ratio2) return -1;

    else if (ratio1 < ratio2) return 1;

    else return 0;

}

void discreteKnapsack(struct Item items[], int n, int capacity) {

    int i, j;

    int dp[n + 1][capacity + 1];

    // Initialize the DP table

    for (i = 0; i <= n; i++) {

        for (j = 0; j <= capacity; j++) {

            if (i == 0 || j == 0)

                dp[i][j] = 0;

            else if (items[i - 1].weight <= j)

                dp[i][j] = (items[i - 1].value + dp[i - 1][j - items[i - 1].weight] > dp[i - 1][j]) ?

                           (items[i - 1].value + dp[i - 1][j - items[i - 1].weight]) :

                           dp[i - 1][j];

            else

                dp[i][j] = dp[i - 1][j];

        }

    }

    printf("Total value obtained for discrete knapsack: %d\n", dp[n][capacity]);

}

void continuousKnapsack(struct Item items[], int n, int capacity) {

    int i;

    double totalValue = 0.0;

    int remainingCapacity = capacity;

    for (i = 0; i < n; i++) {

        if (remainingCapacity >= items[i].weight) {

            totalValue += items[i].value;

            remainingCapacity -= items[i].weight;

        } else {

            totalValue += (double)remainingCapacity / items[i].weight * items[i].value;

            break;

        }

    }

    printf("Total value obtained for continuous knapsack: %.2lf\n", totalValue);

}

int main() {

    int n, capacity, i;

    printf("Enter the number of items: ");

    scanf("%d", &n);

    struct Item items[n];

    printf("Enter the capacity of the knapsack: ");

    scanf("%d", &capacity);

    printf("Enter the value and weight of each item:\n");

    for (i = 0; i < n; i++) {

        scanf("%d %d", &items[i].value, &items[i].weight);

        items[i].ratio = (double)items[i].value / items[i].weight;

    }

    // Sort items based on value-to-weight ratio

    qsort(items, n, sizeof(struct Item), compare);

    discreteKnapsack(items, n, capacity);

    continuousKnapsack(items, n, capacity);

    return 0;

}

OUTPUT:

n items: 4

knap cap:10

val wt for these 4 are:

42 7

12 3

40 4

25 5

ans dis knap is 65

ans con knap 76.00

6. Dynamic Programming method.

 #include <stdio.h>

// Function to find maximum of two integers

int max(int a, int b) {

    return (a > b) ? a : b;

}

// Function to solve 0/1 Knapsack problem

int knapsack(int W, int wt[], int val[], int n) {

    int i, w;

    int K[n + 1][W + 1];

    // Build table K[][] in bottom-up manner

    for (i = 0; i <= n; i++) {

        for (w = 0; w <= W; w++) {

            if (i == 0 || w == 0)

                K[i][w] = 0;

            else if (wt[i - 1] <= w)

                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);

            else

                K[i][w] = K[i - 1][w];

        }

    }

    // K[n][W] contains the maximum value that can be put in a knapsack of capacity W

    return K[n][W];

}

int main() {

    int val[100], wt[100]; // Arrays to store values and weights

    int W, n; // Knapsack capacity and number of items

    printf("Enter the number of items: ");

    scanf("%d", &n);

    printf("Enter the values and weights of %d items:\n", n);

    for (int i = 0; i < n; i++) {

        printf("Enter value and weight for item %d: ", i + 1);

        scanf("%d %d", &val[i], &wt[i]);

    }

    printf("Enter the knapsack capacity: ");

    scanf("%d", &W);

    printf("Maximum value that can be obtained: %d\n", knapsack(W, wt, val, n));

    return 0;

}

OUTPUT:

n items: 4

val wt for all 4;-

42 7

12 3

40 4

25 5

knapsack cap: 10

ans is 65

4. Dijkstra's algorithm

  #include <stdio.h>

#include <stdbool.h>

#include <limits.h>

#define MAX_VERTICES 10  // Maximum number of vertices

#define INF INT_MAX

int minDistance(int dist[], bool sptSet[], int V) {

    int min = INF, min_index;

    for (int v = 0; v < V; v++)

        if (sptSet[v] == false && dist[v] <= min)

            min = dist[v], min_index = v;

    return min_index;

}

void printSolution(int dist[], int V) {

    printf("Vertex \t\t Distance from Source\n");

    for (int i = 0; i < V; i++)

        printf("%d \t\t %d\n", i, dist[i]);

}

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int V) {

    int dist[MAX_VERTICES]; 

    bool sptSet[MAX_VERTICES]; 

    // Initialize all distances as INFINITE and sptSet[] as false

    for (int i = 0; i < V; i++)

        dist[i] = INF, sptSet[i] = false;

    dist[src] = 0;

    // Find shortest path for all vertices

    for (int count = 0; count < V - 1; count++) {

        int u = minDistance(dist, sptSet, V);

        sptSet[u] = true;

        for (int v = 0; v < V; v++)

            if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])

                dist[v] = dist[u] + graph[u][v];

    }

    printSolution(dist, V);

}

int main() {

    int V, E;

    printf("Enter the number of vertices: ");

    scanf("%d", &V);

    printf("Enter the number of edges: ");

    scanf("%d", &E);

    int graph[MAX_VERTICES][MAX_VERTICES] = {{0}};

    printf("Enter the source vertex, destination vertex, and weight for each edge:\n");

    for (int i = 0; i < E; i++) {

        int source, dest, weight;

        scanf("%d %d %d", &source, &dest, &weight);

        graph[source][dest] = weight;

        graph[dest][source] = weight; // Assuming undirected graph

    }

    dijkstra(graph, 0, V);

    return 0;

}

OUTPUT:

vertices:5

edges;7

0 1 2

0 3 6

1 2 3

1 3 8

1 4 5

2 4 7

3 4 9