Enrollment No:202203103510031
Practical 5
Aim: A thief robbing a store finds n items, ith item is worth vi dollars and
weights wi pounds, where vi and wi are integers. He wants to take as valuable
a load as possible, but he can carry atmost W pounds in his knapsack where
W is an integer. Which items should he take, where condition is that he is
allowed to take or select fractional part of an item?
[Hint: Fractional Knapsack (Greedy Approach)]
W = 50, n = 3
Object 1 2 3
Weight (wi) 10 20 30
Value (vi)($) 60 100 150
Code:
#include<stdio.h>
int n,W,i,j,a[100];
float temp,w[100],r[100],v[100],p,weight=0,x[100];
void maxv();
void minw();
void v_w();
void print();
void swap();
void maxv()
{
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(v[i]<v[j])
{
swap();
}
}
}
print();
}
void minw()
{
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
CGPIT/CE/SEM-5/Design and Analysis of Algorithm (CE5002)
15
Enrollment No:202203103510031
if(w[i]>w[j])
{
swap();
}
}
}
print();
}
void v_w()
{
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(r[i]==r[j])
{
if(v[i]<v[j])
{
swap();
}
}
else if(r[i]<r[j])
{
swap();
}
}
}
print();
}
void swap()
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
temp=r[i];
r[i]=r[j];
r[j]=temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
temp=w[i];
w[i]=w[j];
w[j]=temp;
}
void print()
CGPIT/CE/SEM-5/Design and Analysis of Algorithm (CE5002)
16
Enrollment No:202203103510031
{
for(i=0;i<n;i++)
{
if(weight+w[i]<=W)
{
weight=weight+w[i];
}
else
{
x[i]=(W-weight)/w[i];
weight=weight+(x[i]*w[i]);
}
p=p+(x[i]*v[i]);
}
printf("Index Portion Weight Value\tRatio\n");
for(i=0;i<n;i++)
{
printf("%d %.2f %.2f %.2f\t%.2f\n",a[i],x[i],w[i],v[i],r[i]);
x[i]=1;
}
printf("\nTotal Price with optimization is : %f\n",p);
p=weight=0;
}
void main()
{
printf("Enter the number of items : ");
scanf("%d",&n);
printf("Enter required weight : ");
scanf("%d",&W);
printf("\n");
for(i=0;i<n;i++)
{
printf("Enter weight of item %d : ",i+1);
scanf("%f",&w[i]);
printf("Enter value of item %d : ",i+1);
scanf("%f",&v[i]);
printf("\n\n");
a[i]=i+1;
x[i]=1;
r[i]=v[i]/w[i];
}
int c;
printf("1. Maximum v/w\n2. Maximum Value\n3. Minimum Weight\n4. Exit\n");
do
{
printf("Enter your choice : ");
scanf("%d",&c);
switch(c)
CGPIT/CE/SEM-5/Design and Analysis of Algorithm (CE5002)
17
Enrollment No:202203103510031
{
case 1:
v_w();
break;
case 2:
maxv();
break;
case 3:
minw();
break;
case 4:
break;
default:
printf("Enter Correct Choice!!!!\n");
break;
}
}while(c!=4);
}
Output:
CGPIT/CE/SEM-5/Design and Analysis of Algorithm (CE5002)
18
Enrollment No:202203103510031
Practical 6
Aim: Implement job Scheduling algorithm with Deadlines
Code:
#include <stdio.h>
void job (int *,int*,int,int);
void main()
{
printf("Job Scheduling\n");
int profit[20],dead[20],n,i,j,maxdead;
printf("Enter number of element:\n");
scanf("%d",&n);
printf("Enter profit:\n");
for(i=0;i<n;i++)
{
scanf("%d",&profit[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(profit[i]>profit[j])
{
int temp=profit[i];
profit[i]=profit[j];
profit[j]=temp;
}
}
}
printf("Profit in descending order is:");
for(i=0;i<n;i++)
{
printf("%d ",profit[i]);
}
printf("\nEnter deadline according to profit value sorted above :\n");
for(i=0;i<n;i++)
{
scanf("%d",&dead[i]);
}
printf("Enter Maximum deadline:\n");
scanf("%d",&maxdead);
job(profit,dead,n,maxdead);
}
void job(int profit[],int dead[],int n,int maxdead)
{
CGPIT/CE/SEM-5/Design and Analysis of Algorithm (CE5002)
19
Enrollment No:202203103510031
int result[20],total=0,i,j;
for(int i=0;i<maxdead;i++)
{
result[i]=0;
}
for(i=0;i<n;i++)
{
if(result[dead[i]-1]==0)
{
result [dead[i]-1]=profit[i];
total=total+profit[i];
}
else
{
for(int j=dead[i]-1;j>=0;j--)
{
if(result[j]==0)
{
result[j]=profit[i];
total=total+profit[i];
}
}
}
}
printf("Total profit is:%d",total);
printf("\nOutput array is:\n");
for (i=0;i<maxdead;i++)
{
printf("At index %d \n",i+1);
}
}
Output:
CGPIT/CE/SEM-5/Design and Analysis of Algorithm (CE5002)
20
