C program for knapsack algorithm

Answer 1

#include<stdio.h>

#include<conio.h>

int w[10],p[10],v[10][10],n,i,j,cap,x[10]={0};

int max(int i,int j)

{

return ((i>j)?i:j);

}

int knap(int i,int j)

{

int value;

if(v[i][j]<0)

{

if(j<w[i])

value=knap(i-1,j);

else

value=max(knap(i-1,j),p[i]+knap(i-1,j-w[i]));

v[i][j]=value;

}

return(v[i][j]);

}

void main()

{

int profit,count=0;

clrscr();

printf("\nEnter the number of elements\n");

scanf("%d",&n);

printf("Enter the profit and weights of the elements\n");

for(i=1;i<=n;i++)

{

printf("For item no %d\n",i);

scanf("%d%d",&p[i],&w[i]);

}

printf("\nEnter the capacity \n");

scanf("%d",&cap);

for(i=0;i<=n;i++)

for(j=0;j<=cap;j++)

if((i==0)(j==0))

v[i][j]=0;

else

v[i][j]=-1;

profit=knap(n,cap);

i=n;

j=cap;

while(j!=0&&i!=0)

{

if(v[i][j]!=v[i-1][j])

{

x[i]=1;

j=j-w[i];

i--;

}

else

i--;

}

printf("Items included are\n");

printf("Sl.no\tweight\tprofit\n");

for(i=1;i<=n;i++)

if(x[i])

printf("%d\t%d\t%d\n",++count,w[i],p[i]);

printf("Total profit = %d\n",profit);

getch();

}

Answer 2

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

*/