Name : Anubhab Bera
Roll No : 11500123033
CSE A2
4th Sem
Assignment 3
1.Implement Knapsack problem (fractional knapsack) for finding out
maximum profit.
CODE:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int weight;
int profit;
float ratio;
} Item;
int compareRatio(const void *a, const void *b) {
float r1 = ((Item*)a)->ratio;
float r2 = ((Item*)b)->ratio;
return (r1 < r2) ? 1 : (r1 > r2) ? -1 : 0;
}
int compareProfit(const void *a, const void *b) {
return ((Item*)b)->profit - ((Item*)a)->profit;
}
int compareWeight(const void *a, const void *b) {
return ((Item*)a)->weight - ((Item*)b)->weight;
}
float knapsackGreedy(Item items[], int n, int M, int strategy) {
float totalProfit = 0.0;
int remainingCapacity = M;
if (strategy == 1) {
qsort(items, n, sizeof(Item), compareProfit);
} else if (strategy == 2) {
qsort(items, n, sizeof(Item), compareWeight);
} else if (strategy == 3) {
for (int i = 0; i < n; i++) {
items[i].ratio = (float)items[i].profit / items[i].weight;
}
qsort(items, n, sizeof(Item), compareRatio);
}
for (int i = 0; i < n; i++) {
if (items[i].weight <= remainingCapacity) {
totalProfit += items[i].profit;
remainingCapacity -= items[i].weight;
} else {
totalProfit += (float)items[i].profit * remainingCapacity / items[i].weight;
break;
}
}
return totalProfit;
}
int main() {
int n, M;
printf("Enter number of items: ");
scanf("%d", &n);
printf("Enter knapsack capacity: ");
scanf("%d", &M);
Item *items = (Item *)malloc(n * sizeof(Item));
if (!items) {
printf("Memory allocation failed!\n");
return 1;
}
for (int i = 0; i < n; i++) {
printf("Enter weight and profit for item %d: ", i + 1);
scanf("%d %d", &items[i].weight, &items[i].profit);
items[i].ratio = (float)items[i].profit / items[i].weight;
}
printf("\nMaximized profit using the largest profit strategy: %.2f\n", knapsackGreedy(items, n,
M, 1));
printf("Maximized profit using the smallest weight strategy: %.2f\n", knapsackGreedy(items, n,
M, 2));
printf("Maximized profit using the largest profit-to-weight ratio strategy: %.2f\n",
knapsackGreedy(items, n, M, 3));
free(items);
return 0;
}
Output
2. Implement job sequencing with deadline problem for finding out optimal
scheduling of jobs.
CODE:
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a job
struct Job {
int id; // Job ID
int profit; // Profit of the job
int deadline; // Deadline of the job
};
// Comparison function to sort jobs based on profit in descending order
int compareJobs(const void *a, const void *b) {
return ((struct Job *)b)->profit - ((struct Job *)a)->profit;
}
// Function to find the maximum profit job sequence
void jobSequencing(struct Job jobs[], int n) {
// Find the maximum deadline
int maxDeadline = 0;
for (int i = 0; i < n; i++) {
if (jobs[i].deadline > maxDeadline) {
maxDeadline = jobs[i].deadline;
}
}
// Create a time slot array to track available time slots
int *timeSlot = (int *)malloc(maxDeadline * sizeof(int));
if (!timeSlot) {
printf("Memory allocation failed!\n");
return;
}
for (int i = 0; i < maxDeadline; i++) {
timeSlot[i] = -1; // Initialize all slots to -1 (meaning empty)
}
// Sort the jobs by profit in decreasing order
qsort(jobs, n, sizeof(struct Job), compareJobs);
// To store the result
int totalProfit = 0;
int jobCount = 0;
// Go through each job and try to schedule it
for (int i = 0; i < n; i++) {
// Find a slot for this job
for (int j = jobs[i].deadline - 1; j >= 0; j--) {
if (j < maxDeadline && timeSlot[j] == -1) {
timeSlot[j] = jobs[i].id; // Assign job to the slot
totalProfit += jobs[i].profit; // Add profit
jobCount++; // Increase the count of jobs
break;
}
}
}
// Print the result
printf("Total jobs selected: %d\n", jobCount);
printf("Total profit: %d\n", totalProfit);
printf("Jobs selected: ");
for (int i = 0; i < maxDeadline; i++) {
if (timeSlot[i] != -1) {
printf("%d ", timeSlot[i]);
}
}
printf("\n");
// Free allocated memory
free(timeSlot);
}
int main() {
int n;
// User input for the number of jobs
printf("Enter the number of jobs: ");
scanf("%d", &n);
struct Job *jobs = (struct Job *)malloc(n * sizeof(struct Job));
if (!jobs) {
printf("Memory allocation failed!\n");
return 1;
}
// User input for job details
for (int i = 0; i < n; i++) {
jobs[i].id = i + 1; // Job ID (1 to n)
printf("Enter profit for job %d: ", jobs[i].id);
scanf("%d", &jobs[i].profit);
printf("Enter deadline for job %d: ", jobs[i].id);
scanf("%d", &jobs[i].deadline);
}
// Call the function to find the job sequence
jobSequencing(jobs, n);
// Free allocated memory
free(jobs);
return 0;
}
output :
