Warshalls algorithm using dynamic programming in C Programming

ALGORITHM

Warshalls algorithm using dynamic programming in C Programming

#include
#include
#include

#define MAX 7

void fnWarshall(int aiAdj[MAX][MAX],int iN)
{
int iI,iJ,iK;
for(iK=0;iK
{
printf("\nTranstive Closure : %d\n",iK+1);
for(iI=0;iI
{
for(iJ=0;iJ
{
aiAdj[iI][iJ]=(aiAdj[iI][iJ]||(aiAdj[iI][iK] && aiAdj[iK][iJ]));
printf(" %d ",aiAdj[iI][iJ]);
}
printf("\n");
}
}
}


void main()
{
int aiAdj[MAX][MAX],iI,iJ,iN;
clrscr();
printf("Enter the no of Vertices : ");
scanf("%d",&iN);
printf("\nEnter the adjency Matrix \n ");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiAdj[iI][iJ]);
fnWarshall(aiAdj,iN);
getch();
}

/*
OutPut
Enter the no of Vertices : 4

Enter the adjency Matrix

0 1 0 0
0 0 0 0
0 0 0 1
1 0 0 0

Transtive Closure : 1
0 1 0 0
0 0 0 0
0 0 0 1
1 1 0 0

Transtive Closure : 2
0 1 0 0
0 0 0 0
0 0 0 1
1 1 0 0

Transtive Closure : 3
0 1 0 0
0 0 0 0
0 0 0 1
1 1 0 0

Transtive Closure : 4
0 1 0 0
0 0 0 0
1 1 0 1
1 1 0 0

*/

TSP in C Programming

ALGORITHM

TSP in C Programming

#include
#include

#define MAX 9

struct Tour
{
int iCost;
int iCount;
// int aiCity[MAX];
int aiVisit[MAX];
}cTour,oTour;

int fnVisited(int adj)
{
int iI;
for(iI=0;iI
if(cTour.aiVisit[adj]==adj)
return 1;
return 0;
}

void OptimalTour(int iCity,int iCost,int iN,int aiCost[MAX][MAX])
{
int iI;
// printf("/nHai");
cTour.iCost +=iCost;
cTour.aiVisit[cTour.iCount]=0;
// printf("\ncTour.iCount : %d",cTour.iCount);
if(cTour.iCost
{
oTour.iCost=cTour.iCost;
oTour=cTour;
}
printf("\nCost is : %d",cTour.iCost);
printf("\nPaths are : %d \n",cTour.iCount);
for(iI=0;iI<=cTour.iCount;iI++)
{
printf(" %d ",cTour.aiVisit[iI]);
// getch();
}
// cTour.iCount--;
// cTour.aiVisit[cTour.iCount]=-1;
cTour.iCost-=aiCost[iCity][0];
cTour.iCount--;
}


void fnTsp(int iCity,int iCost,int iN,int aiCost[MAX][MAX])
{
int adj;
cTour.iCost +=iCost;
cTour.aiVisit[cTour.iCount++]=iCity;
if(cTour.iCount==iN && aiCost[iCity][0]!=999)
{
OptimalTour(iCity,aiCost[iCity][0],iN,aiCost);
getch();
}
else
{
for(adj=1;adj
if(!fnVisited(adj) && cTour.iCost+aiCost[adj][iCity]
fnTsp(adj,aiCost[adj][iCity],iN,aiCost);
}
cTour.iCost -=iCost;
cTour.aiVisit[cTour.iCount]=-1;
cTour.iCount-=1;
}

void main()
{
int iN,aiCost[MAX][MAX];

int iI,iJ;

clrscr();
printf("Enter the number of nodes : ");
scanf("%d",&iN);
printf("\nEnter the cost matrix\n");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiCost[iI][iJ]);
for(iI=0;iI
cTour.aiVisit[iI]=-1;
cTour.iCost=0;
cTour.iCount=0;
oTour.iCost=999;
fnTsp(0,0,iN,aiCost);
getch();
}

N Queens problem solving using BackTracking in C Programming

ALGORITHM

N Queens problem solving using BackTracking in C Programming

#include
#include
#include

#define MAX=10


int fnPlace(int iK,int iI,int iX[10])
{
int iJ;
for(iJ=1;iJ<=iK-1;iJ++)
{
if(iX[iJ]==iI||abs(iJ-iK)==abs(iX[iJ]-iI))
return 0;
}
return 1;
}

void fnQueens(int iK,int iN)
{
int iI,iJ,iL;
static int iCount,iX[10];
for(iI=1;iI<=iN;iI++)
{
if(fnPlace(iK,iI,iX))
{
iX[iK]=iI;
if(iK==iN)
{
printf("\nFeassible solution : %d",++iCount);
printf("\nSolutions are : ");
for(iJ=1;iJ<=iN;iJ++)
printf(" %d ",iX[iJ]);
for(iJ=1;iJ<=iN;iJ++)
{
printf("\n");
for(iL=1;iL<=iN;iL++)
{
if(iL==iX[iJ])
printf(" X ");
else
printf(" 0 ");
}
}
}
else
fnQueens(iK+1,iN);
}
}
}


void main()
{
int iNo;
clrscr();
printf("Enter the no of Queenes : ");
scanf("%d",&iNo);
fnQueens(1,iNo);
getch();
}

/*
Enter the no of Queenes : 4

Feassible solution : 1
Solutions are : 2 4 1 3
0 X 0 0
0 0 0 X
X 0 0 0
0 0 X 0
Feassible solution : 2
Solutions are : 3 1 4 2
0 0 X 0
X 0 0 0
0 0 0 X
0 X 0 0

*/

Prims algorithm using greedy method in C Programming

ALGORITHM

Prims algorithm using greedy method in C Programming

#include
#include

#define MAX 10
#define NOPATH 999


void fnPrims(int aiWei[MAX][MAX],int iSize)
{
int aiNear[MAX],iI,iJ,iCost=NOPATH,iK,iL,iM,iZ=1,iSmall;
static int min_cost,Sol[NOPATH][2];
for(iI=1;iI<=iSize;iI++)
for(iJ=1;iJ<=iSize;iJ++)
if(aiWei[iI][iJ]
{
iCost=aiWei[iI][iJ];
iK=iI;
iL=iJ;
}
Sol[1][1]=iK;
Sol[1][2]=iL;
min_cost=min_cost+iCost;
for(iJ=1;iJ<=iSize;iJ++)
aiNear[iJ]=999;
aiNear[iK]=0;
aiNear[iL]=0;
for(iI=1;iI<=iSize;iI++)
{
if(aiNear[iI]!=0)
{
if(aiWei[iL][iI]
aiNear[iI]=iL;
else
aiNear[iI]=iK;
}
}
printf("\nStep : 1");
printf("\n________");
for(iI=1;iI<=iSize;iI++)
printf("\naiNear[%d] = %d ",iI,aiNear[iI]);
for(iI=2;iI<=iSize-1;iI++)
{
iJ=1;
iSmall=999;
printf("Step : %d\n",iI);
printf("______________");
for(iM=1;iM<=iSize;iM++)
if(aiNear[iM]!=0)
{
printf("\naiWei[%d][%d]=%d",iM,aiNear[iM],aiWei[iM][aiNear[iM]]);
if(iSmall>aiWei[iM][aiNear[iM]])
{
iJ=iM;
iSmall=aiWei[iM][aiNear[iM]];
}
}
getch();
Sol[iI][1]= iJ;
printf("\nThe iJ value : %d\n",iJ);
Sol[iI][2]=aiNear[iJ];
printf("\nCost is : %d",aiWei[iJ][aiNear[iJ]]);
min_cost=min_cost+aiWei[iJ][aiNear[iJ]];
printf("\nMinimum Cost : %d\n",min_cost);
aiNear[iJ]=0;
for(iM=1;iM<=iSize;iM++)
{
if(aiNear[iM]!=0)
if(aiWei[iM][iJ]
aiNear[iM]=iJ;
}
}
if(min_cost>=NOPATH)
printf("\nNOT SPANNING TREE");
else
{
printf("\nPaths are : \n");
for(iI=1;iI
{
for(iJ=1;iJ<3;ij++)
printf(" %d ",Sol[iI][iJ]);
printf("\n");
}
printf("\nThe cost is : %d",min_cost);
}
}

void main()
{
int iSize,iI,iJ,aiWei[MAX][MAX];
clrscr();
printf("\n\tPRIMS ALGORITHM");
printf("\nEnter the no vertices : ");
scanf("%d",&iSize);
printf("\nEnter the Weighted matrix.\n");
for(iI=1;iI<=iSize;iI++)
for(iJ=1;iJ<=iSize;iJ++)
scanf("%d",&aiWei[iI][iJ]);
fnPrims(aiWei,iSize);
getch();
}



/*

OUTPUT:

PRIMS ALGORITHM
Enter the no vertices : 5

Enter the Weighted matrix.
999 4 8 999 999
4 999 6 999 2
8 6 999 1 5
999 999 1 999 3
999 2 5 3 999

Step : 1
________
aiNear[1] = 3
aiNear[2] = 3
aiNear[3] = 0
aiNear[4] = 0
aiNear[5] = 4 Step : 2
______________
aiWei[1][3]=8
aiWei[2][3]=6
aiWei[5][4]=3

The iJ value :5

Cost is : 3
Minimum Cost : 4
Step : 3
______________
aiWei[1][3]=8
aiWei[2][5]=2
The iJ value : 2

Cost is : 2
Minimum Cost : 6
Step : 4
______________
aiWei[1][2]=4
The iJ value : 1

Cost is : 4
Minimum Cost : 10

Paths are :
3 4
5 4
2 5
1 2

The cost is : 10

*/

MERGE SORT USING DIVIDE & CONQUER METHOD in C PROGRAMMING

ALGORITHM

MERGE SORT USING DIVIDE & CONQUER METHOD in C PROGRAMMING

#include
#include

/*
Funtion : fnMerge
Description : To Merge the B and C array in to A array
Parameters : A,B,C Arrays and their sizes
Retutn : Nothing.
*/

void fnMerge(int aiB[20],int iP,int aiC[20],int iQ,int aiA[20])
{
int iI,iJ,iK,iX,iY;
iI=0;
iJ=0;
iK=0;
while(iI
{
if(aiB[iI]
{
aiA[iK] = aiB[iI];
iI++;
}
else
{
aiA[iK]=aiC[iJ];
iJ++;
}
iK++;
}
if(iJ
for(iX=iJ;iX
aiA[iK]=aiC[iX];
else
for(iX=iI;iX
aiA[iK]=aiB[iX];
}

/*
Funtion : fnDivide
Description : To Divide the A array in to B and C array
Parameters : A Array and it size
Retutn : Nothing.
*/

void fnDivide(int aiA[20],int iN)
{
int iI,iJ,iK,aiB[20],aiC[20];
iI=0;
iJ=0;iK=0;
if(iN>1)
{
for(iI=0,iJ=0;iI
aiB[iJ]=aiA[iI];
for(iK=0;iI
aiC[iK]=aiA[iI];
fnDivide(aiB,iJ);
fnDivide(aiC,iK);
fnMerge(aiB,iJ,aiC,iK,aiA);
}
}


void main()
{
int aiA[20],iI,iN;
clrscr();
printf("\n\tMERGE SORT USING DIVIDE & CONQUER METHOD");
printf("\nEnter the Value of n : ");
scanf("%d",&iN);
printf("\nEnter the array elements \n");
for(iI=0;iI
scanf("%d",&aiA[iI]);
fnDivide(aiA,iN);
printf("\nSorted List.");
for(iI=0;iI
printf("%5d",aiA[iI]);
getch();
}


/*
OUTPUT:


MERGE SORT USING DIVIDE & CONQUER METHOD


Enter the Value of n : 7

Enter the array elements

23 45 1 -90 78 666 -12

Sorted List. -90 -12 1 23 45 78 666

*/

KNAPSACK problem using greedy method in C Programming

ALGORITHM
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

*/

Travelling sales man problem in C Programming

ALGORITHM
C Programming - Travelling sales man problem solving using Back Tracking

#include
#include
#include

#define MAX 10

struct Tour
{
int iCount;
int aiCity[MAX];
}cTour;

void fnDisplay(int cCity,int iN)
{
int iI;
static int count;
cTour.aiCity[cTour.iCount]=0;
printf("\nSOLUTION:%d\n",count++);
printf("\nPath is : \n");
for(iI=0;iI<=cTour.iCount;iI++)
printf(" %d ",cTour.aiCity[iI]);
}

int fnVisited(int adj)
{
int iI;
for(iI=0;iI
if(cTour.aiCity[iI]==adj)
return 1;
return 0;
}

int fnPromising(int cCity,int adj,int aiAdj[MAX][MAX])
{
if(!fnVisited(adj) && aiAdj[cCity][adj]!=0)
return 1;
return 0;
}

void fnSearch(int cCity,int iN,int aiAdj[MAX][MAX])
{
int adj;
cTour.aiCity[cTour.iCount++]=cCity;
if(cTour.iCount==iN && aiAdj[cCity][0]!=0)
{
fnDisplay(cCity,iN);
getch();
}
else
for(adj=0;adj
{
if(fnPromising(cCity,adj,aiAdj))
{
fnSearch(adj,iN,aiAdj);
}
}
cTour.aiCity[cTour.iCount]=-1;
cTour.iCount-=1;
}

void main()
{
int iN,iI,aiAdj[MAX][MAX],iJ;
clrscr();
cTour.iCount=0;
printf("\nEnter the no of cities : ");
scanf("%d",&iN);
printf("\nEnter the adjency matrix : \n");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiAdj[iI][iJ]);
for(iI=0;iI
cTour.aiCity[iI]=-1;
fnSearch(0,iN,aiAdj);
getch();
}

/*
OUTPUT:

Enter the no of cities : 4

Enter the adjency matrix :
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0

SOLUTION:0

Path is :
0 1 2 3 0
SOLUTION:1

Path is :
0 3 2 1 0

*/

C Programming - GraphTraversal using BackTracking

ALGORITHM
C Programming - GraphTraversal using BackTracking

#include
#include

int aiQueue[10],iFront=-1,iRear=-1;


void fnDfs(int aiAdj[7][7],int iN,int iI,int aiVisit[7])
{
int iJ;
aiVisit[iI]=1;
printf(" %d ",iI+1);
for(iJ=0;iJ
if(aiAdj[iI][iJ]==1 && aiVisit[iJ]==0)
fnDfs(aiAdj,iN,iJ,aiVisit);
}


int Empty()
{
if(iRear==-1 && iFront==-1)
return 0;
return 1;
}

void fnEnQueue(int aiQueue[7],int iI)
{
if(iFront==-1 && iRear==-1)
iFront++;
iRear++;
aiQueue[iRear]=iI;
}

int fnDeQueue(int aiQueue[7],int iI)
{
iI=aiQueue[iFront];
if(iFront==iRear)
iRear=iFront=-1;
else
iFront++;
return iI;
}


void fnBfs(int aiAdj[7][7],int iN,int iI,int aiVisit[7])
{
int iJ,iX;
aiVisit[iI]=1;
printf(" %d ",iI+1);
for(iJ=0;iJ
{
if(aiAdj[iI][iJ]==1 && aiVisit[iJ]==0)
{
fnEnQueue(aiQueue,iJ);
aiVisit[iJ]=1;
}
}
if(iFront==-1 && iRear==-1)
return;
iX=fnDeQueue(aiQueue,iI);
fnBfs(aiAdj,iN,iX,aiVisit);
}

void main()
{
int iChoice,iI,iJ,aiAdj[7][7],aiVisit[7],iNo;
clrscr();
printf("\n\t\tGRAPH TRAVERSAL");
printf("\n\t1.BIRTH FIRST SEARCH");
printf("\n\t2.DEPTH FIRST SEARCH");
printf("\n\t3.EXIT");
printf("\nEnter the no of vertices : ");
scanf("%d",&iNo);
printf("\nEnter the adjency matrix ");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiAdj[iI][iJ]);
do
{
printf("\nEnter your choice : ");
scanf("%d",&iChoice);
switch(iChoice)
{
case 1://Depthfirst search
for(iI=0;iI
aiVisit[iI]=0;
fnDfs(aiAdj,iNo,0,aiVisit);
break;
case 2://Birthfirst search
for(iI=0;iI
aiVisit[iI]=0;
fnBfs(aiAdj,iNo,0,aiVisit);
break;
case 3://Exit
break;
}
}while(iChoice!=3);
}

/*

GRAPH TRAVERSAL
1.BIRTH FIRST SEARCH
2.DEPTH FIRST SEARCH
3.EXIT
Enter the no of vertices : 6

Enter the adjency matrix
0 1 0 0 0 1
0 0 1 0 0 1
0 0 0 1 0 1
0 0 0 0 0 0
1 0 0 1 0 0
0 0 0 0 1 0

Enter your choice : 1
1 2 3 4 6 5
Enter your choice : 2
1 2 6 3 5 4
Enter your choice : 3

*/

C Programming - Floyds algorithm using dynamic programming

ALGORITHM
C Programming - Floyds algorithm using dynamic programming

#include
#include
#include
#include

#define MAX 7

void fnFloyds(int aiCost[MAX][MAX],int iN)
{
int iI,iJ,iK;
for(iK=0;iK
{
printf("\nTranstive Closure : %d\n",iK+1);
for(iI=0;iI
{
for(iJ=0;iJ
{
aiCost[iI][iJ]=min(aiCost[iI][iJ],(aiCost[iI][iK] + aiCost[iK][iJ]) );
printf(" %d ",aiCost[iI][iJ]);
}
printf("\n");
}
}
}


void main()
{
int aiCost[MAX][MAX],iI,iJ,iN;
clrscr();
printf("Enter the no of Vertices : ");
scanf("%d",&iN);
printf("\nEnter the Cost Matrix \n ");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiCost[iI][iJ]);
fnFloyds(aiCost,iN);
getch();
}

C Programming - Program to find optimal binary search tree using dynamic programming

ALGORITHM

C Programming - Program to find optimal binary search tree using dynamic programming

#include
#include

# define INFINITE 999

void fnDisplay(float afA[7][7],int iN)
{
int iI,iJ;
for(iI=1;iI<=iN+1;iI++)
{
for(iJ=0;iJ<=iN;iJ++)
if(iJ>=iI-1)
printf(" %4.2f ",afA[iI][iJ]);
else
printf(" ");
printf("\n");
}
}

void fnTree(int iFirst,int iLast,float afRoot[7][7])
{
int iK;
if(iFirst>iLast || iLast==0)
return;
iK=afRoot[iFirst][iLast];
printf(" %d ",iK);
fnTree(iFirst,iK-1,afRoot);
fnTree(iK+1,iLast,afRoot);
}

void fnOptimalBST(float afFrequency[7],int iN)
{
int iI,iJ,iK,iS,iD,iRootmin;
float afMain[7][7],afRoot[7][7],fSum,fMin;
for(iI=1;iI<=iN;iI++)
{
afMain[iI][iI-1]=0;
afMain[iI][iI]=afFrequency[iI];
afRoot[iI][iI]=iI;
}
afMain[iN+1][iN]=0;
for(iD=1;iD {
for(iI=1;iI<=iN-iD;iI++)
{
iJ=iI+iD;
fMin=INFINITE;
for(iK=iI;iK<=iJ;iK++)
if((afMain[iI][iK-1]+afMain[iK+1][iJ]) {
fMin=afMain[iI][iK-1]+afMain[iK+1][iJ];
iRootmin=iK;
}
afRoot[iI][iJ]=iRootmin;
fSum=afFrequency[iI];
for(iS=iI+1;iS<=iJ;iS++)
fSum+=afFrequency[iS];
afMain[iI][iJ]=fMin+fSum;
}
}
printf("\n\nMain table:\n");
fnDisplay(afMain,iN);
printf("\n\nRoot table:\n");
fnDisplay(afRoot,iN);
printf("\n\nOptimal Binary search tree is :\n\t");
fnTree(1,iN,afRoot);
printf("\n\nCost is %f",afMain[1][iN]);
}

void main()
{
int iI,iN;
float afFrequency[7];
clrscr();
printf("Enter the no of nodes : ");
scanf("%d",&iN);
printf("\nEnter the frequency of the nodes : \n");
for(iI=1;iI<=iN;iI++)
scanf("%f",&afFrequency[iI]);
fnOptimalBST(afFrequency,iN);
getch();
}


/* OUTPUT:
-------
How many nodes: 5

Enter the search probabilities:
.1 .2 .3 .2 .2


Main table:
0.00 0.10 0.40 1.00 1.40 2.00
0.00 0.20 0.70 1.10 1.70
0.00 0.30 0.70 1.20
0.00 0.20 0.60
0.00 0.20
0.00


Root table:
0.00 1.00 2.00 2.00 3.00 3.00
0.00 2.00 3.00 3.00 3.00
0.00 3.00 3.00 4.00
0.00 4.00 4.00
0.00 5.00
0.00


Optimal Binary search tree is :
3 2 1 4 5

Cost is 2.000000
*/


Comment and discuss your doubts

C Programming - Knap Sack problem solving using Branch and bound method

ALGORITHM

C Programming - Knap Sack problem solving using Branch and bound method

#include
#include
#include

int fnBound(int iCp,int iCw,int iK,int iMax,int aiP[9],int iItem,int aiW[9])
{
float iUb;
if(iK+1 iUb=iCp+(iMax - iCw)*(aiP[iK+1]/(float)aiW[iK+1]);
else
iUb=iCp;
return iUb;
}

void fnBranch_bound(int iK,int iCp,int iCw,int iMax,int aiW[9],int aiPr[9],int iItem)
{
static int sSol[9];
static int sFp,sFw;
int iI,iJ;
if(iCw+aiW[iK]<=iMax)
{
sSol[iK]=1;
if(iK fnBranch_bound(iK+1,iCp+aiPr[iK],iCw+aiW[iK],iMax,aiW,aiPr,iItem);
if(iK==iItem && (iCp+aiPr[iK])>sFp)
{
printf("\nSolution vectors are : ");
for(iI=0;iI printf(" %d ",sSol[iI]);
sFp=iCp+aiPr[iK];
sFw=iCw+aiW[iK-1];
printf("\nProfit is : %d",sFp);
printf("\nWeight is : %d",sFw);
}
}
if (fnBound(iCp,iCw,iK,iMax,aiPr,iItem,aiW)>sFp)
{
sSol[iK]=0;
if(iK fnBranch_bound(iK+1,iCp,iCw,iMax,aiW,aiPr,iItem);
if(iK==iItem && iCp>sFp)
{
sFp=iCp;
sFw=iCw;
for(iJ=0;iJ printf(" %d ",sSol[iJ]);
printf("\nProfit is : %d",sFp);
printf("\nWeight is : %d",iCw);
}
}
}



void main()
{
int iItem,aiWeight[9],aiProfit[9],iI,iJ,iMax;
void fnBranch_bound(int iK,int iCp,int iCw,int iMax,int aiW[9],int aiPr[9],int iItem);
clrscr();
printf("Knap Sack Problem Solving using branch and bound method.\n");
printf("How many item do you want : ");
scanf("%d",&iItem);
printf("Enter the weight and profit for each item \n");
printf("Weight Profit\n");
for(iJ=0;iJ scanf("%d%d",&aiWeight[iJ],&aiProfit[iJ]);
printf("Enter the maximum capacity of knapsack : ");
scanf("%d",&iMax);
fnBranch_bound(0,0,0,iMax,aiWeight,aiProfit,iItem);
getch();
}

/* OUT PUT:
Knap Sack Problem Solving using branch and bound method.
How many item do you want : 8
Enter the weight and profit for each item
Weight Profit
1 11
11 21
21 31
23 33
33 43
43 53
45 55
55 65

Enter the maximum capacity of knapsack : 110

Solution vectors are : 1 1 1 1 1 0 0 0
Profit is : 139
Weight is : 89

Solution vectors are : 1 1 1 1 0 1 0 0
Profit is : 149
Weight is : 99

Solution vectors are : 1 1 1 1 0 0 1 0
Profit is : 151
Weight is : 101

Solution vectors are : 1 1 1 0 1 1 0 0
Profit is : 159
Weight is : 109

*/

Comment your doubts and discuss

C Programming - Travelling sales man problem solving using Back Tracking

ALGORITHM

C Programming - Travelling sales man problem solving using Back Tracking

#include
#include
#include

#define MAX 10

struct Tour
{
int iCount;
int aiCity[MAX];
}cTour;

void fnDisplay(int cCity,int iN)
{
int iI;
static int count;
cTour.aiCity[cTour.iCount]=0;
printf("\nSOLUTION:%d\n",count++);
printf("\nPath is : \n");
for(iI=0;iI<=cTour.iCount;iI++)
printf(" %d ",cTour.aiCity[iI]);
}

int fnVisited(int adj)
{
int iI;
for(iI=0;iI
if(cTour.aiCity[iI]==adj)
return 1;
return 0;
}

int fnPromising(int cCity,int adj,int aiAdj[MAX][MAX])
{
if(!fnVisited(adj) && aiAdj[cCity][adj]!=0)
return 1;
return 0;
}

void fnSearch(int cCity,int iN,int aiAdj[MAX][MAX])
{
int adj;
cTour.aiCity[cTour.iCount++]=cCity;
if(cTour.iCount==iN && aiAdj[cCity][0]!=0)
{
fnDisplay(cCity,iN);
getch();
}
else
for(adj=0;adj
{
if(fnPromising(cCity,adj,aiAdj))
{
fnSearch(adj,iN,aiAdj);
}
}
cTour.aiCity[cTour.iCount]=-1;
cTour.iCount-=1;
}

void main()
{
int iN,iI,aiAdj[MAX][MAX],iJ;
clrscr();
cTour.iCount=0;
printf("\nEnter the no of cities : ");
scanf("%d",&iN);
printf("\nEnter the adjency matrix : \n");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiAdj[iI][iJ]);
for(iI=0;iI
cTour.aiCity[iI]=-1;
fnSearch(0,iN,aiAdj);
getch();
}