Scribd
Upload
268 views4 pages

Knapsack Code - C Source Code

The document presents a C code implementation of the knapsack problem using a greedy approach. It allows the user to input the size of the knapsack and the number of objects, along with their weights and profits, and then calculates the maximum profit achievable. The output includes the fractions of each object included in the knapsack, total weight, and total profit.

Uploaded by

For_Educational_Purpose
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
268 views4 pages

Knapsack Code - C Source Code

The document presents a C code implementation of the knapsack problem using a greedy approach. It allows the user to input the size of the knapsack and the number of objects, along with their weights and profits, and then calculates the maximum profit achievable. The output includes the fractions of each object included in the knapsack, total weight, and total profit.

Uploaded by

For_Educational_Purpose
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 4

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

You might also like