KNAPSACK problem using greedy method in C Programming

#include

#include

typedef struct

{

char acName[5];

int iProfit,iWeight;

}Item;

void fnDisplay(Item aiA[10],int iN)

{

int iI;

printf("\nNAME WEIGHT PROFIT\n");

for(iI=0;iI

printf("%s%8d%8d\n",

aiA[iI].acName,aiA[iI].iWeight,aiA[iI].iProfit);

}

void fnUpdate(Item aiA[10],int iN)

{

int iI,iJ;

Item t;

for(iI=0;iI

for(iJ=iI+1;iJ

if((float)(aiA[iI].iProfit)/(aiA[iI].iWeight)

<(float)(aiA[iJ].iProfit)/(aiA[iJ].iWeight))

{

t=aiA[iI];

aiA[iI]=aiA[iJ];

aiA[iJ]=t;

}

}

void fnKnapsack(int iM,Item aiA[10],float aiX[10],int iN)

{

int iI,iJ,iCur;

float iProfit=0;

for(iI=1;iI<=iN;iI++)

aiX[iI]=0;

iCur=iM;

for(iI=0;iI

{

if(aiA[iI].iWeight>iCur)

break;

else

{

aiX[iI]=1;

iCur=iCur -aiA[iI].iWeight;

iProfit=iProfit+aiA[iI].iProfit;

}

}

if(iI<=iN)

{

aiX[iI]=iCur/(float)aiA[iI].iWeight;

iProfit=iProfit+aiA[iJ].iProfit*aiX[iI];

}

printf("\nThe Profit is : %f",iProfit);

}

void main()

{

Item aiA[10];

int iN,iI,iM;

float aiX[10],fProfit;

clrscr();

printf("How many items : ");

scanf("%d",&iN);

printf("\nNAME WEIGHT PROFIT\n");

for(iI=0;iI

{

scanf("%s",&aiA[iI].acName);

scanf("%d%d",&aiA[iI].iWeight,&aiA[iI].iProfit);

}

printf("\nEnter the knapsack capacity : ");

scanf("%d",&iM);

printf("\nThe Orignal List \n");

fnDisplay(aiA,iN);

getch();

fnUpdate(aiA,iN);

printf("\nUPdate List\n");

fnDisplay(aiA,iN);

fnKnapsack(iM,aiA,aiX,iN);

printf("\nThe items insert into knapsack is : ");

printf("\nNAME WEIGHT\n");

for(iI=0;iI

if(aiX[iI]!=0)

printf("%3s %8f\n",aiA[iI].acName,aiX[iI]);

getch();

}

/*

How many items : 4

NAME WEIGHT PROFIT

a 12 3

b 4 6

c 8 5

d 7 4

Enter the knapsack capacity : 20

The Orignal List

NAME WEIGHT PROFIT

a 12 3

b 4 6

c 8 5

d 7 4

UPdate List

NAME WEIGHT PROFIT

b 4 6

c 8 5

d 7 4

a 12 3

The Profit is : 15.250000

The items insert into knapsack is :

NAME WEIGHT

b 1.000000

c 1.000000

d 1.000000

a 0.083333

*/

Resources

Top Categories

Product

Company