#include <stdio.
h>
#define MAX 50
int p[MAX], w[MAX], x[MAX];
double maxprofit;
int n, m, i;
void greedyKnapsack(int n, int w[], int p[], int m)
double ratio[MAX];
// Calculate the ratio of profit to weight for each item
for (i = 0; i < n; i++)
ratio[i] = (double)p[i] / w[i];
// Sort items based on the ratio in non-increasing order
for (i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (ratio[i] < ratio[j])
double temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;
int temp2 = w[i];
w[i] = w[j];
w[j] = temp2;
temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
int currentWeight = 0;
maxprofit = 0.0;
// Fill the knapsack with items
for (i = 0; i < n; i++)
if (currentWeight + w[i] <= m)
x[i] = 1; // Item i is selected
currentWeight += w[i];
maxprofit += p[i];
else
// Fractional part of item i is selected
x[i] = (m - currentWeight) / (double)w[i];
maxprofit += x[i] * p[i];
break;
printf("Optimal solution for greedy method: %.1f\n", maxprofit);
printf("Solution vector for greedy method: ");
for (i = 0; i < n; i++)
printf("%d\t", x[i]);
int main()
printf("Enter the number of objects: ");
scanf("%d", &n);
printf("Enter the objects' weights: ");
for (i = 0; i < n; i++)
scanf("%d", &w[i]);
printf("Enter the objects' profits: ");
for (i = 0; i < n; i++)
scanf("%d", &p[i]);
printf("Enter the maximum capacity: ");
scanf("%d", &m);
greedyKnapsack(n, w, p, m);
return 0;
}
#include<stdio.h>
int w[10],p[10],n;
int max(int a,int b)
return a>b?a:b;
int knap(int i,int m)
if(i==n) return w[i]>m?0:p[i];
if(w[i]>m) return knap(i+1,m);
return max(knap(i+1,m),knap(i+1,m-w[i])+p[i]);
int main()
int m,i,max_profit;
printf("\nEnter the no. of objects:");
scanf("%d",&n);
printf("\nEnter the knapsack capacity:");
scanf("%d",&m);
printf("\nEnter profit followed by weight:\n");
for(i=1; i<=n; i++)
scanf("%d %d",&p[i],&w[i]);
max_profit=knap(1,m);
printf("\nMax profit=%d",max_profit);
return 0;
}
#include<stdio.h>
#include<conio.h>
int temp[10],k=0;
void sort(int a[][10],int id[],int n)
int i,j;
for(i=1; i<=n; i++)
if(id[i]==0)
id[i]=-1;
temp[++k]=i;
for(j=1; j<=n; j++)
if(a[i][j]==1 && id[j]!=-1)
id[j]--;
i=0;
void main()
int a[10][10],id[10],n,i,j;
printf("\nEnter the n value:");
scanf("%d",&n);
for(i=1; i<=n; i++)
id[i]=0;
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
id[j]++;
sort(a,id,n);
if(k!=n)
printf("\nTopological ordering not possible");
else
printf("\nTopological ordering is:");
for(i=1; i<=k; i++)
printf("%d ",temp[i]);
getch();
}4
#include<stdio.h>
#define INF 999
void dijkstra(int c[10][10],int n,int s,int d[10])
int v[10],min,u,i,j;
for(i=1; i<=n; i++)
d[i]=c[s][i];
v[i]=0;
v[s]=1;
for(i=1; i<=n; i++)
min=INF;
for(j=1; j<=n; j++)
if(v[j]==0 && d[j]<min)
min=d[j];
u=j;
v[u]=1;
for(j=1; j<=n; j++)
if(v[j]==0 && (d[u]+c[u][j])<d[j])
d[j]=d[u]+c[u][j];
int main()
int c[10][10],d[10],i,j,s,sum,n;
printf("\nEnter n value:");
scanf("%d",&n);
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&c[i][j]);
printf("\nEnter the souce node:");
scanf("%d",&s);
dijkstra(c,n,s,d);
for(i=1; i<=n; i++)
printf("\nShortest distance from %d to %d is %d",s,i,d[i]);
return 0;
