Akshita Bhawsar|EN22CS301098

Experiment-09

Aim- Implement and analyze the time complexity of 0/1 Knapsack.

Theory-
The 0/1 Knapsack Problem is a dynamic programming problem where items have specific
weights and values, and the goal is to maximize the total value in a knapsack of fixed capacity,
ensuring that each item is either taken or left (no fractional selection allowed). Since the greedy
approach does not guarantee an optimal solution, dynamic programming is used by solving
smaller subproblems and storing the results in a DP table.

For example, given items (weight, value) as (1, 10), (2, 20), (3, 30) and a knapsack capacity of
5, the optimal solution is to take items with weights 2 and 3, achieving a total value of 50. The
bottom-up DP approach constructs a 2D table where dp[i][j] represents the maximum value
attainable with the first i items and weight j. The time complexity of this approach is O(n × W),
making it efficient for moderate-sized inputs but impractical for large constraints.

Algorithm-
1. Initialize a DP Table K[n+1][W+1]:
• K[i][w] represents the maximum value that can be obtained using the first i items and
a knapsack capacity of w.
• The first row (K[0][w]) and first column (K[i][0]) are set to 0 because an empty
knapsack or no items lead to 0 value.

2. Iterate Over Items and Capacities:

• For each item i (1 to n):
o For each capacity w (1 to W):
▪ Case 1: Item is too heavy to include (wt[i-1] > w)
▪ Copy the value from the previous row:
K[i][w]=K[i−1][w]K[i][w] = K[i-1][w]K[i][w]=K[i−1][w]

▪ Case 2: Item can be included (wt[i-1] \leq w)

▪ Compute the maximum value between:
▪ Excluding the item (K[i-1][w])
▪ Including the item (val[i-1] + K[i-1][w - wt[i-1]])
K[i][w]=max(K[i−1][w],val[i−1]+K[i−1][w−wt[i−1]])K[i][w]

56
 Akshita Bhawsar|EN22CS301098

3. Return the Final Solution:

• The maximum value that can be stored in the knapsack is found at K[n][W].

4. Measure Execution Time:

• Record start time before calling knapsack(W, wt, val, n).
• Record end time after execution.
• Compute execution time as:
cpu_time_used=end−start/(CLOCKS_PER_SEC)

Code-
#include <stdio.h>
#include <time.h>
// Function to solve the 0/1 Knapsack problem using Dynamic Programming
int knapsack(int W, int wt[], int val[], int n) {
int K[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = (val[i - 1] + K[i - 1][w - wt[i - 1]] > K[i - 1][w]) ?
val[i - 1] + K[i - 1][w - wt[i - 1]] : K[i - 1][w];
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main() {
int n, W;
printf("Enter number of items: ");
scanf("%d", &n);

int val[n], wt[n];

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

57
 Akshita Bhawsar|EN22CS301098

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

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

printf("Enter knapsack capacity: ");

scanf("%d", &W);

clock_t start, end;

double cpu_time_used;
start = clock();
int maxValue = knapsack(W, wt, val, n);
end = clock();

cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Maximum value in Knapsack = %d\n", maxValue);
printf("Execution time: %f seconds\n", cpu_time_used);
return 0;
}

Output-

Advantages-
1. Guaranteed Optimal Solution – The dynamic programming approach ensures the best
possible answer.
2. Solves Combinatorial Optimization Problems – Useful in budget allocation, cargo
loading, and resource allocation scenarios.

58
 Akshita Bhawsar|EN22CS301098

3. Can Be Extended – Variants like bounded/unbounded knapsack and multi-dimensional

knapsack can be solved using similar approaches.

Disadvantages-
1. High Time Complexity – The O(n × W) complexity becomes infeasible for large inputs.
2. Requires Large Memory – The DP table can take up too much space, making it difficult
to implement for large values of n and W.
3. Not Suitable for Real-Time Applications – The computation overhead makes it
impractical for scenarios requiring quick decision-making.

Time Complexity-
• Best Case: O(n × W) (Runs fully since DP must fill the table).
• Average Case: O(n × W) (DP complexity remains the same regardless of input).
• Worst Case: O(n × W) (DP always fills the table).

Space Complexity-
• Space Complexity: O(n × W) (can be O(W) if optimized).

59
 Akshita Bhawsar|EN22CS301098

Experiment-10

Aim- Implement and analyze the time complexity of N-Queens problem.

Theory-
The N-Queens problem is a backtracking problem that involves placing N queens on an N × N
chessboard such that no two queens attack each other. Since a queen can attack in the same
row, column, and diagonals, the challenge is to find all possible placements that satisfy this
constraint. The recursive backtracking approach places queens one row at a time and checks if
the placement is safe before proceeding.

For example, in the 8-Queens problem, the goal is to place 8 queens on an 8×8 board such that
no two queens threaten each other. A solution is built row by row, backtracking when no valid
position is found. This approach ensures all possible configurations are explored efficiently.
The time complexity is O(N!) in the worst case, making it computationally expensive for large
values of N. The problem is widely used in AI, constraint satisfaction problems, and chess
algorithms.

Algorithm-
1. Initialize the Board: Create an N×NN \times NN×N chessboard initialized with 0, where
1 represents a queen and 0 represents an empty space.
2. Recursive Function solveNQueens(board, col):
• If all queens are placed (i.e., col >= N), print the board and return true.
• For each row in the current column, check if placing a queen there is safe using the
isSafe(board, row, col) function.
• If safe, place the queen (board[row][col] = 1) and recursively solve for the next column
(solveNQueens(board, col + 1)).
• If placing the queen in the current row does not lead to a solution, backtrack by
removing the queen (board[row][col] = 0).

3. Safety Check Function isSafe(board, row, col):

• Check the left side of the row: Ensure no queen is already placed in the same row on
the left.
• Check the upper left diagonal: Ensure no queen is placed in the upper-left diagonal.
• Check the lower left diagonal: Ensure no queen is placed in the lower-left diagonal.

60
 Akshita Bhawsar|EN22CS301098

4. Driver Function solve():

• Initialize the board as a 2D array filled with 0.
• Call solveNQueens(board, 0).
• If no solution is found, print "No solution exists".

Code-

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 4 // Default size, can be changed

// Function to print the solution

void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%c ", board[i][j] ? 'Q' : '-');
printf("\n");
}
printf("\n");
}

// Function to check if a queen can be placed at board[row][col]

int isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++) // Check row on left side
if (board[row][i])
return 0;

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) // Upper diagonal left
if (board[i][j])
return 0;

for (int i = row, j = col; i < N && j >= 0; i++, j--) // Lower diagonal left
if (board[i][j])

61
 Akshita Bhawsar|EN22CS301098

return 0;

return 1;
}

// Recursive function to solve N-Queens problem

int solveNQueens(int board[N][N], int col) {
if (col >= N) {
printSolution(board);
return 1; // A solution is found
}

int res = 0;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
res = solveNQueens(board, col + 1) || res; // Recur to place rest of queens
board[i][col] = 0; // Backtrack
}
}
return res;
}

// Main function to solve the N-Queens problem

void solve() {
int board[N][N] = {0};
if (!solveNQueens(board, 0))
printf("No solution exists\n");
}

int main() {
clock_t start, end;
double cpu_time_used;

62
 Akshita Bhawsar|EN22CS301098

start = clock();
solve();
end = clock();

cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Execution time: %f seconds\n", cpu_time_used);

return 0;
}

Output-

Advantages-
1. Demonstrates Backtracking Efficiency – A great example of constraint satisfaction using
backtracking.
2. Used in AI and Game Theory – Helps in chess algorithms, robotics, and AI-based decision
making.
3. Can Be Optimized – Techniques like bitwise operations and branch pruning improve
efficiency for larger N values.

Disadvantages-
1. Exponential Time Complexity – The worst-case complexity is O(N!), making it infeasible
for large N.
2. Requires Extensive Backtracking – Many configurations need to be explored before
reaching a valid solution.

63
 Akshita Bhawsar|EN22CS301098

3. Hard to Generalize for Variants – Modifications like placing additional constraints can
make the problem even more complex.

Time Complexity-
• Best Case: O(N) (If an early conflict is detected, recursive calls stop quickly).
• Average Case: O(N!) (Recursive backtracking explores valid positions)..
• Worst Case: O(N!) (Explores all possible queen placements).

Space Complexity-
• Space Complexity: O(N) (for storing queen positions).

64