9. Write a program to perform Knapsack problem using Greedy solution.
#include<stdio.h>
int main()
{
float weight[50],profit[50],ratio[50],totalvalue,temp,capacity,amount;
int n,i,j;
clrscr();
printf("Enter the number of item:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter weight and profit for item:\n");
scanf("%f%f",&weight[i],&profit[i]);
}
printf("Enter the capacity of knapsack:\n");
scanf("%f",&capacity);
for(i=0;i<n;i++)
ratio[i]=profit[i]/weight[i];
for(i=0;i<n;i++)
for(j=i+1;j<n;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;
}
printf("Knapsack problem using greedy algorithm\n");
for(i=0;i<n;i++)
{
if(weight[i]>capacity)
break;
else
{
totalvalue=totalvalue+profit[i];
capacity=capacity-weight[i];
}
}
if(i<n)
totalvalue=totalvalue+(ratio[i]*capacity);
printf("\n the maximum value is %f\n",totalvalue);
getch();
}
10. Write a program to implement dynamic programming algorithm for the 0 / 1 Knapsack program.
#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,v[20],w[20],n,m;
void knap(int[],int[],int,int);
clrscr();
printf("\n Enter the number of objects:\n");
scanf("%d",&n);
printf("\n Enter the knapsack capacity:\n");
scanf("%d",&m);
printf("\n Enter the weights of object:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("\n Enter the profits of the object:\n");
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
knap(v,w,n,m);
getch();
}
void knap(int v[],int w[],int n,int m)
{
int i,j,k[20][20];
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||j==0)
k[i][j]=0;
else if(j<w[i])
{
k[i][j]=k[i-1][j];
}
else
{
if(k[i-1][j]>k[i-1][j-w[i]]+v[i])
{
k[i][j]=k[i-1][j];
}
else
{
k[i][j]=k[i-1][j-w[i]]+v[i];
}
}
}
}
printf("\n Maximum profit is=%d",k[n][m]);
getch();
}
11. Write a program that implements Prim’s algorithm to generate minimum cost spanning tree.
#include<stdio.h>
int ne=1,min_cost=0;
void main()
{
int n,i,j,min,cost[20][20],a,u,b,v,source,visited[20];
clrscr();
printf("\nEnter the number of elements:\n");
scanf("%d",&n);
printf("\n Enter the cost matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
{
cost[i][j]=999;
}
}
}
for(i=1;i<n;i++)
visited[i]=0;
printf("\n Enter the root node:");
scanf("%d",&source);
visited[source]=1;
printf("\n Minimum cost spanning tree is\n");
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
if(visited[u]=0||visited[v]==0)
{
printf("\n edge %d \t(%d->%d)=%d\n",ne++,a,b,min);
min_cost=min_cost+min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimum cost=%d \n",min_cost);
getch();
}
12. Write a program that implements Kruskal’s algorithm to generate minimum cost spanning tree.
#include<stdio.h>
int ne=1,min_cost=0;
void main()
{
int n,i,j,min,cost[20][20],a,u,b,v,source,visited[20],parent[20];
clrscr();
printf("Enter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the cost matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
{
cost[i][j]=999;
}
}
}
for(i=1;i<n;i++)
visited[i]=0;
printf("\n Enter the root node:");
scanf("%d",&source);
visited[source]=1;
printf("Minimum cost spanning tree is\n");
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
printf("\n edge %d\t(%d->%d)=%d\n",ne++,a,b,min);
min_cost=min_cost+min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimum cost=%d",min_cost);
getch();
}