Thursday, October 7, 2010

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();
}

Saturday, June 26, 2010

Convert String to Date in Java

Convert String to Date in Java and add months

import java.util.Date;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.text.ParseException;
import java.util.Calendar;
import java.util.Date;
/**
*
* @author Karthik Prabhu
*/
public class DateDemo
{
public static void main(String[] args)
{
DateFormat df = new SimpleDateFormat("dd/MM/yyyy");

try
{
Date today = df.parse("1/1/2010");
System.out.println("Date = " + df.format(today));
Calendar c=Calendar.getInstance();
c.setTime(today);
c.add(Calendar.DAY_OF_MONTH,90); //add 90 days
String str=df.format(c.getTime());

System.out.println(str);

} catch (ParseException e)
{
e.printStackTrace();
}

}
}

Get cash from your website. Sign up as affiliate.


Friday, April 16, 2010

Symbian Os Introduction

Check out this SlideShare Presentation:

Thursday, March 25, 2010

Speech by Chetan Bhagat at Symbiosis

TRUE MESSAGE!! Read with Patience....


Speech by Chetan Bhagat at Symbiosis ...


Don't just have career or academic goals. Set goals to give you a balanced, successful life. I use the word balanced before successful. Balanced means ensuring your health, relationships, mental peace are all in good order.
There is no point of getting a promotion on the day of your breakup. There is no fun in driving a car if your back hurts. Shopping is not enjoyable if your mind is full of tensions.

"Life is one of those races in nursery school where you have to run with a marble in a spoon kept in your mouth. If the marble falls, there is no point coming first. Same is with life where health and relationships are the marble. Your striving is only worth it if there is harmony in your life. Else, you may achieve the success, but this spark, this feeling of being excited and alive, will start to die.

One thing about nurturing the spark - don't take life seriously. Life is not meant to be taken seriously, as we are really temporary here. We are like a pre-paid card with limited validity. If we are lucky, we may last another 50 years. And 50 years is just 2,500 weekends. Do we really need to get so worked up?

It's ok, bunk a few classes, scoring low in couple of papers, goof up a few interviews, take leave from work, fall in love, little fights with your spouse. We are people, not programmed devices.


"Don't be serious, be sincere."!

Thursday, March 18, 2010

Friday, January 29, 2010

Programming Contest




TOP Programming Contest

1)SIGMOD Programming contest - prize 5,000 USD

http://dbweb.enst.fr/events/sigmod10contest/#details

2) Student Programming contest

http://www.realtimeworlds.com/2009/12/15/student-programming-contest-2010/

3) MICS contest for students

http://www.cs.uwec.edu/MICS/students/programming_contest.php

4) multi Agent contest

http://www.multiagentcontest.org/

5)TopCoder

http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static

6)Interview Street - facebook interview coding test

https://www.interviewstreet.com/challenges/

7) Codility

http://codility.com/

Online Placement Preparation

Online Aptitude Test

The following websites are very useful to practice placement aptitude test papers.
Try to solve all the question then you have more than 70% chance to get a job in MNCs.

1) http://www.indiabix.com

2) http://www.tcyonline.com/india/Home

3) http://koolkampus.com/campus-crash-course.php

4) http://www.test4free.com/

5) http://www.eskill.com/aptitude.htm