//Knapsack using Dynamic Programming
#include <stdio.h>
#define MAX_ITEMS 100
#define MAX_CAPACITY 1000
int max(int a, int b)
{
return (a > b) ? a : b;
}
void knapsack(int weights[], int values[], int numItems, int capacity)
{
int dp[MAX_ITEMS + 1][MAX_CAPACITY + 1],i,w;
// Initialize the dp array
for ( i = 0; i <= numItems; i++)
{
for ( w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
{
dp[i][w] = 0; // Base case: 0 items or 0 capacity
} else if (weights[i - 1] <= w)
{
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
} else
{
dp[i][w] = dp[i - 1][w];
}
}
}
// The maximum value that can be obtained
printf("Maximum value in Knapsack = %d\n", dp[numItems][capacity]);
// Optional: Print items included in the knapsack
printf("Items included:\n");
w = capacity;
for ( i = numItems; i > 0 && dp[i][w] > 0; i--)
{
if (dp[i][w] != dp[i - 1][w])
{
printf("Item %d (Weight: %d, Value: %d)\n", i, weights[i - 1], values[i - 1]);
w -= weights[i - 1];
}
}
}
int main()
{
int numItems, capacity,i;
printf("Enter the number of items: ");
scanf("%d", &numItems);
int weights[MAX_ITEMS];
int values[MAX_ITEMS];
printf("Enter the weights of the items:\n");
for ( i = 0; i < numItems; i++)
{
scanf("%d", &weights[i]);
}
printf("Enter the values of the items:\n");
for ( i = 0; i < numItems; i++)
{
scanf("%d", &values[i]);
}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
knapsack(weights, values, numItems, capacity);
return 0;
}
OUTPUT:
//Knapsack using Back tracking
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int weights[], int values[], int n, int capacity) {
// Base case: No items left or no capacity left
if (n == 0 || capacity == 0) {
return 0;
}
// If the weight of the nth item is more than capacity, skip it
if (weights[n - 1] > capacity) {
return knapsack(weights, values, n - 1, capacity);
} else {
// Return the maximum of two cases: 1. nth item included 2. nth item not included
return max(values[n - 1] + knapsack(weights, values, n - 1, capacity - weights[n - 1]),
knapsack(weights, values, n - 1, capacity));
}
}
int main()
{
int n, capacity,i;
printf("Enter the number of items: ");
scanf("%d", &n);
int weights[n], values[n];
printf("Enter the weights of the items:\n");
for (i = 0; i < n; i++) {
scanf("%d", &weights[i]);
}
printf("Enter the values of the items:\n");
for (i = 0; i < n; i++) {
scanf("%d", &values[i]);
}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
int maxValue = knapsack(weights, values, n, capacity);
printf("Maximum value in Knapsack = %d\n", maxValue);
return 0;
}
OUTPUT:
//N-Queen Problem
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 20
int board[MAX_N][MAX_N];
int N;
void printSolution()
{
int i,j;
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
printf("%d ", board[i][j]);
}
printf("\n");
}
printf("\n");
}
bool isSafe(int row, int col)
{
int i,j;// Check this column on upper side
for (i = 0; i < row; i++)
{
if (board[i][col] == 1)
{
return false;
}
}
// Check upper diagonal on left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (board[i][j] == 1)
{
return false;
}
}
// Check upper diagonal on right side
for (i = row, j = col; i >= 0 && j < N; i--, j++)
{
if (board[i][j] == 1)
{
return false;
}
}
return true;
}
bool solveNQueens(int row)
{
int col;
if (row >= N)
{
printSolution();
return true; // Return true to find all solutions, change to false if only one solution is
needed
}
bool foundSolution = false;
for (col = 0; col < N; col++)
{
if (isSafe(row, col))
{
board[row][col] = 1; // Place the queen
foundSolution = solveNQueens(row + 1) || foundSolution; // Recursively place
queens
board[row][col] = 0; // Backtrack
}
}
return foundSolution;
}
int main()
{
int i,j,N;
printf("Enter the number of queens (N): ");
scanf("%d", &N);
// Initialize the board
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
board[i][j] = 0; // Empty
}
}
if (!solveNQueens(0)) {
printf("No solution exists for N = %d\n", N);
}
return 0;
}
OUTPUT:
//Travelling salesperson using Branch & Bound
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 20
#define INF INT_MAX
int cost[MAX][MAX]; // Cost matrix
int n; // Number of cities
typedef struct {
int path[MAX]; // Path taken
int cost; // Cost of the current path
int level; // Level in the tree
} Node;
int min(int a, int b) {
return (a < b) ? a : b;
}
// Function to create a new node
Node* createNode(int path[], int level, int cost) {
Node* newNode = (Node*)malloc(sizeof(Node));
int i;
for (i = 0; i < n; i++)
newNode->path[i] = path[i];
newNode->level = level;
newNode->cost = cost;
return newNode;
}
// Function to perform Branch and Bound TSP
void tsp() {
int minCost = INF,city,i;
Node* root = createNode((int[]){0}, 0, 0); // Starting from city 0
root->path[0] = 0;
Node* queue[MAX]; // Simple array to store nodes
int front = 0, rear = 0;
// Enqueue the root node
queue[rear++] = root;
while (front < rear) {
Node* current = queue[front++];
// If we have reached the last city
if (current->level == n - 1) {
// Check if we can return to the start
int finalCost = current->cost + cost[current->path[current->level]][0];
minCost = min(minCost, finalCost);
free(current);
continue;
}
// Explore children nodes
for (city = 0; city < n; city++) {
// Skip already visited cities
if (city == current->path[current->level] || city == 0) continue;
int newCost = current->cost + cost[current->path[current->level]][city];
if (newCost < minCost) { // Only consider nodes that do not exceed the min cost
found so far
int newPath[MAX];
for ( i = 0; i <= current->level; i++)
newPath[i] = current->path[i];
newPath[current->level + 1] = city;
Node* child = createNode(newPath, current->level + 1, newCost);
queue[rear++] = child;
}
}
free(current);
}
printf("Minimum cost: %d\n", minCost);
}
int main() {
int i,j;
printf("Enter the number of cities: ");
scanf("%d", &n);
printf("Enter the cost matrix:\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &cost[i][j]);
tsp();
return 0;
}
OUTPUT:
