7.
Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack problems
using greedy approximation method.
#include <stdio.h>
#define MAX_ITEMS 50
void sortItems(float weight[], float profit[], float ratio[], int n) {
// Sort items in non-increasing order of profit-to-weight ratio
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (ratio[i] < ratio[j]) {
// Swap ratios
float temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
// Swap weights
temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;
// Swap profits
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
}
void solveContinuousKnapsack(float weight[], float profit[], int n, float capacity) {
float ratio[MAX_ITEMS], totalValue = 0;
// Calculate profit-to-weight ratio for each item
for (int i = 0; i < n; i++)
ratio[i] = profit[i] / weight[i];
// Sort items
sortItems(weight, profit, ratio, n);
// Fill the knapsack with items
for (int i = 0; i < n && capacity > 0; i++) {
if (weight[i] <= capacity) {
capacity -= weight[i];
totalValue += profit[i];
} else {
totalValue += ratio[i] * capacity;
break;
}
}
printf("Maximum value for continuous knapsack problem: %.2f\n", totalValue);
}
void solveDiscreteKnapsack(float weight[], float profit[], int n, float capacity) {
float ratio[MAX_ITEMS], totalValue = 0;
// Calculate profit-to-weight ratio for each item
for (int i = 0; i < n; i++)
ratio[i] = profit[i] / weight[i];
// Sort items
sortItems(weight, profit, ratio, n);
// Fill the knapsack with items
for (int i = 0; i < n && capacity > 0; i++) {
if (weight[i] <= capacity) {
capacity -= weight[i];
totalValue += profit[i];
}
}
printf("Maximum value for 0/1 knapsack problem: %.2f\n", totalValue);
}
int main() {
int n;
float capacity;
int choice;
printf("Enter the number of items: ");
scanf("%d", &n);
float weight[MAX_ITEMS], profit[MAX_ITEMS];
printf("Enter the weight and profit of each item:\n");
for (int i = 0; i < n; i++) {
printf("Item %d: ", i + 1);
scanf("%f %f", &weight[i], &profit[i]);
}
printf("Enter the capacity of the knapsack: ");
scanf("%f", &capacity);
printf("Choose the type of knapsack problem to solve:\n");
printf("1. Continuous (Fractional) Knapsack\n");
printf("2. Discrete (0/1) Knapsack\n");
scanf("%d", &choice);
if (choice == 1) {
solveContinuousKnapsack(weight, profit, n, capacity);
} else if (choice == 2) {
solveDiscreteKnapsack(weight, profit, n, capacity);
} else {
printf("Invalid choice.\n");
}
return 0;
}
8.Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive
integers whose sum is equal to a given positive integer d.
#include <stdio.h>
#define MAX_SIZE 10
int set[MAX_SIZE], subset[MAX_SIZE];
int n, targetSum, flag = 0;
void display(int count) {
printf("{");
for (int i = 0; i < count; i++) {
printf("%d", subset[i]);
if (i < count - 1) {
printf(", ");
}
}
printf("}\n");
}
void findSubset(int sum, int index, int count) {
if (sum == targetSum) {
flag = 1;
display(count);
return;
}
if (sum > targetSum || index >= n) {
return;
}
subset[count] = set[index];
findSubset(sum + set[index], index + 1, count + 1);
findSubset(sum, index + 1, count);
}
int main() {
printf("Enter the number of elements in the set: ");
scanf("%d", &n);
printf("Enter the elements of the set: ");
for (int i = 0; i < n; i++) {
scanf("%d", &set[i]);
}
printf("Enter the target sum: ");
scanf("%d", &targetSum);
printf("Subsets with sum %d:\n", targetSum);
findSubset(0, 0, 0);
if (!flag) {
printf("There is no solution\n");
}
return 0;
}
EXPERIMENT-12
Design and implement C/C++ Program for N Queen's problem using Backtracking.
About the program:
The N-Queens problem is a classic chessboard puzzle where the goal is to place N queens on
an N×N chessboard so that no two queens threaten each other. It's a well-known example of a
combinatorial optimization problem with applications in computer science, mathematics, and
artificial intelligence. Backtracking is a common algorithmic technique used to solve this
problem by systematically exploring all possible configurations of queen placements,
backtracking whenever a conflict arises until a valid solution is found or all possibilities are
exhausted.
Program:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int totalSolutions = 0; // Global variable to store the total number of solutions
// Function to print the board
void printSolution(int board[], int N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i] == j)
printf(" Q ");
else
printf(" - ");
}
printf("\n");
}
}
// Function to check if it's safe to place a queen at board[row][col]
bool isSafe(int board[], int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
// Recursive function to solve N Queen's problem
void solveNQUtil(int board[], int row, int N) {
if (row >= N) {
printSolution(board, N);
printf("\n");
totalSolutions++;
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(board, row, col)) {
board[row] = col;
solveNQUtil(board, row + 1, N);
board[row] = -1; // backtrack
}
}
}
// Main function to solve N Queen's problem
void solveNQ(int N) {
int board[N];
for (int i = 0; i < N; i++) {
board[i] = -1;
}
solveNQUtil(board, 0, N);
}
// Driver program
int main() {
int N;
printf("Enter the number of queens: ");
scanf("%d", &N);
solveNQ(N);
printf("Total solutions: %d\n", totalSolutions);
return 0;
}
Sample Output:
Enter the number of queens: 4
- Q - -
- - - Q
Q - - -
- - Q -
- - Q -
Q - - -
- - - Q
- Q - -
Total solutions: 2
#include <stdio.h>
#define MAX_SIZE 10
int set[MAX_SIZE], subset[MAX_SIZE];
int n, targetSum, flag = 0;
void display(int count) {
printf("{");
for (int i = 0; i < count; i++) {
printf("%d", subset[i]);
if (i < count - 1) {
printf(", ");
}
}
printf("}\n");
}
void findSubset(int sum, int index, int count) {
if (sum == targetSum) {
flag = 1;
display(count);
return;
}
if (sum > targetSum || index >= n) {
return;
}
subset[count] = set[index];
findSubset(sum + set[index], index + 1, count + 1);
findSubset(sum, index + 1, count);
}
int main() {
printf("Enter the number of elements in the set: ");
scanf("%d", &n);
printf("Enter the elements of the set: ");
for (int i = 0; i < n; i++) {
scanf("%d", &set[i]);
}
printf("Enter the target sum: ");
scanf("%d", &targetSum);
printf("Subsets with sum %d:\n", targetSum);
findSubset(0, 0, 0);
if (!flag) {
printf("There is no solution\n");
}
Sample Output:
Enter the number of elements in the set: 8
Enter the elements of the set: 1 2 3 4 5 6 7 8
Enter the target sum: 8
Subsets with sum 8:
{1, 2, 5}
{1, 3, 4}
{1, 7}
{2, 6}
{3, 5}
{8}
