Notes

program 1.
#include<stdio.h>
void printMaxActivities(int s[], int f[], int n)
{
int i, j;

printf ("Following activities are selected n");

// The first activity always gets selected
i = 0;
printf("%d ", i);

// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
}
}
}

// driver program to test above function
int main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}


program 2 :

#include <stdio.h>



int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W

int knapsack(int W, int wt[], int val[], int n)

{

int i, w;

int K[n+1][W+1];



// Build table K[][] in bottom up manner

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

{

for (w = 0; w <= W; w++)

{

if (i==0 || w==0)

K[i][w] = 0;

else if (wt[i-1] <= w)

K[i][w] = max(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 val[] = {60, 100, 120};

int wt[] = {10, 20, 30};

int W = 50;

int n = sizeof(val)/sizeof(val[0]);

printf("nValue = %d", knapsack(W, wt, val, n));

return 0;

}

program 3


# include<stdio.h>

void knapsack(int n, float weight[], float profit[], float capacity) {
float x[20], tp = 0;
int i, j, u;
u = capacity;

for (i = 0; i < n; i++)
x[i] = 0.0;

for (i = 0; i < n; i++) {
if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}

if (i < n)
x[i] = u / weight[i];

tp = tp + (x[i] * profit[i]);

printf("nThe result vector is:- ");
for (i = 0; i < n; i++)
printf("%ft", x[i]);

printf("nMaximum profit is:- %f", tp);

}

int main() {
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;

printf("nEnter the no. of objects:- ");
scanf("%d", &num);

printf("nEnter the wts and profits of each object:- ");
for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i], &profit[i]);
}

printf("nEnter the capacityacity of knapsack:- ");
scanf("%f", &capacity);

for (i = 0; i < num; i++) {
ratio[i] = profit[i] / weight[i];
}

for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) {
if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;

temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;

temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}

knapsack(num, weight, profit, capacity);
return(0);
}


program 4:


#include<stdio.h>
int n,i,j,k,t;
int check(int s[],int p)
{ int ptr=0;
for(int i=0;i<n;i++)
{if(s[i]==p)
ptr++;
}
if(ptr==0)
return 1;
else
return 0;
}

int main()
{
printf("enter the no of jobs : ");
scanf("%d",&n);
int slot[n],profit,p[n],d[n];
for(i=0;i<n;i++)
{printf("n enter the profit of job #%d :",i+1);
scanf("%d",&p[i]);
printf("n enter the deadline of job #%d :",i+1);
scanf("%d",&d[i]);
}

for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(p[i]<p[j])
{ t=p[i];
p[i]=p[j];
p[j]=t;
t=d[i];
d[i]=d[j];
d[j]=t;
}

for(i=0;i<n;i++)
slot[i]=0;

for(i=0;i<n;i++)
for(j=d[i];j>0;j--)
{if(check(slot,j)==1)
{slot[i]=j;
break;}
}

printf("nn INDEX PROFIT DEADLINE SLOT ALLOTTED ");
for(i=0;i<n;i++)
{if(slot[i]>0)
printf("nn %d %d %d [%d - %d]", i+1,p[i],d[i],(slot[i]-1),slot[i]);
else
printf("nn %d %d %d REJECTED", i+1,p[i],d[i]);
}
}