Roll No.
104179
Assignment-Knapsack problem solving using greedy approach.
C Code-
#include<stdio.h>
#include<conio.h>
#define max 10
void main()
{
clrscr();
float x[max],w,wt[max],pt[max],s[max],p;
int cap,major,num,i,j,temp,temp1;
printf("\nEnter da size of knapsack-");
scanf("%d",&cap);
printf("Enter da number of objects-");
scanf("%d",&num);
printf("\n\t INPUT ");
for(i=0;i<num;i++)
{
printf("\n\tweight of Object%d -",i+1);
scanf("%f",&wt[i]);
printf("\n\tprofit of Object%d -",i+1);
scanf("%f",&pt[i]);
}
/*for(i=0;i<num;i++)
{
s[i]=pt[i]/wt[i];
printf("\ns[i] is %f"s[i]);
} */
for(i=0;i<num;i++)
{
for(j=0;j<(num-1);j++)
{
if((pt[j]/wt[j])<=(pt[j+1]/wt[j+1]))
{
temp=pt[j];
pt[j]=pt[j+1];
pt[j+1]=temp;
temp=wt[j];
wt[j]=wt[j+1];
wt[j+1]=temp;
}
}
}
printf("\n\tSorting in decreasing order of p[i]/wt[i] - \n");
for(i=0;i<num;i++)
{
printf("\nPROFIT : %f \tWEIGHT : %f\n",pt[i],wt[i]);
}
major=cap;
for(i=0;i<num;i++)
x[i]=0.0;
for(i=0;i<num;i++)
{
if(wt[i]>major)
break;
x[i]=1.0;
major=major-wt[i];
}
if(i<=num)
{
x[i]=major/wt[i];
// u=0;
}
p=0.0;w=0.0;
for(i=0;i<num;i++)
{
p=p+x[i]*pt[i];
w=w+x[i]*wt[i];
}
printf("\n\nFractions Are - \n");
for(i=0;i<num;i++)
printf("\nX[%d] = %f",i,x[i]);
printf("\n\nTOTAL WEIGHT : %f",w);
printf("\nTOTAL PROFIT : %f",p);
getch();
}
Output-
Enter da size of knapsack-20
Enter da number of objects-3
INPUT
weight of Object1 -18
profit of Object1 -25
weight of Object2 -15
profit of Object2 -24
weight of Object3 -10
profit of Object3 -15
Sorting in decreasing order of p[i]/wt[i] -
PROFIT : 24.000000 WEIGHT : 15.000000
PROFIT : 15.000000 WEIGHT : 10.000000
PROFIT : 25.000000 WEIGHT : 18.000000
Fractions Are -
X[0] = 1.000000
X[1] = 0.500000
X[2] = 0.000000
TOTAL WEIGHT : 20.000000
TOTAL PROFIT : 31.500000
////////////////////////////////////////////////////
Enter da size of knapsack-15
Enter da number of objects-7
INPUT
Enter da size of knapsack-15
Enter da number of objects-7
INPUT
weight of Object1 -2
profit of Object1 -10
weight of Object2 -3
profit of Object2 -5
weight of Object3 -5
profit of Object3 -15
weight of Object4 -7
profit of Object4 -7
weight of Object5 -1
profit of Object5 -6
weight of Object6 -4
profit of Object6 -18
weight of Object7 -1
profit of Object7 -3
PROFIT : 10.000000 WEIGHT : 2.000000
PROFIT : 18.000000 WEIGHT : 4.000000
PROFIT : 3.000000 WEIGHT : 1.000000
PROFIT : 15.000000 WEIGHT : 5.000000
PROFIT : 5.000000 WEIGHT : 3.000000
PROFIT : 7.000000 WEIGHT : 7.000000
Fractions Are -
X[0] = 1.000000
X[1] = 1.000000
X[2] = 1.000000
X[3] = 1.000000
X[4] = 1.000000
X[5] = 0.666667
X[6] = 0.000000
TOTAL WEIGHT : 15.000000
TOTAL PROFIT : 55.333332
