C code for Travelling Sales Person Problem – Branch and Bound Approach


/*Branch and Bound Algorithm for Travelling Sales Person*/

#include<stdio.h>

#include<conio.h>

int a[10][10],visited[10],n,cost=0;


void get()

{

int i,j;

printf(“Enter No. of Cities: “);

scanf(“%d”,&n);

printf(“\nEnter Cost Matrix: \n”);

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

{

printf(“\n Enter Elements of Row # : %d\n”,i+1);

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

scanf(“%d”,&a[i][j]);

visited[i]=0;

}

printf(“\n\nThe cost list is:\n\n”);

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

{

printf(“\n\n”);

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

printf(“\t%d”,a[i][j]);

}

}


void mincost(int city)

{

int i,ncity;

visited[city]=1;

printf(“%d –>”,city+1);

ncity=least(city);

if(ncity==999)

{

ncity=0;

printf(“%d”,ncity+1);

cost+=a[city][ncity];

return;

}

mincost(ncity);

}


int least(int c)

{

int i,nc=999;

int min=999,kmin;

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

{

if((a[c][i]!=0)&&(visited[i]==0))

if(a[c][i]<min)

{

min=a[i][0]+a[c][i];

kmin=a[c][i];

nc=i;

}

}

if(min!=999)

cost+=kmin;

return nc;

}


void put()

{

printf(“\n\nMinimum cost:”);

printf(“%d”,cost);

}

void main()

{

clrscr();

get();

printf(“\n\nThe Path is:\n\n”);

mincost(0);

put();

getch();

}

Input Sample:

No. of Nodes : 6

Cost Matrix:

99            10            15            20            99            8

5              99            9              10            8              99

6              13            99            12            99            5

8              8              9              99            6              99

99            10            99            6              99            99

10            99            5              99            99            99

C Code for Knapsack Problem using Backtracking Approach


/* knapsack  problem using backtracking*/

/* Variable Description….

n   – Total no. of items available

w[] – Weight of each item

p[] – Profit of each item

m   – Maximum Capacity of the Sack

unit[] – Profit of each item per Unit p[]/w[]

x[] – Final list of items put into the Sack

y[] – Intermediate list of selected items

fp  – Final Profit

fw  – Final Weight

cp  – Current Profit

cw  – Current Weight

*/

#include <stdio.h>

#include <conio.h>

#define max 10

int w[max],i,j,p[max];

int n,m;

float unit[max];

int y[max],x[max],fp=-1,fw;

void get()

{

printf(“\n Enter total number of items: “);

scanf(“%d”,&n);

printf(“\n Enter the Maximum capacity of the Sack: “);

scanf(“%d”,&m);

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

{

printf(“\n Enter the weight of the item # %d : “,i+1);

scanf(“%d”,&w[i]);

printf(“\n Enter the profit of the item # %d : “, i+1);

scanf(“%d”, &p[i]);

}

}

void show()

{

float s=0.0;

printf(“\n\tItem\tWeight\tCost\tUnit Profit\tSelected “);

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

printf(“\n\t%d\t%d\t%d\t%f\t%d”,i+1,w[i],p[i],unit[i],x[i]);

printf(“\n\n The Sack now holds following items : “);

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

if(x[i]==1)

{

printf(“%d\t”,i+1);

s += (float) p[i] * (float) x[i];

}

printf(“\n Maximum Profit: %f “,s);

}

/*Arrange the item based on high profit per Unit*/

void sort()

{

int t,t1;

float t2;

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

unit[i] = (float) p[i] / (float) w[i];

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

{

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

{

if(unit[i]  < unit[j])

{

t2 = unit[i];

unit[i] = unit[j];

unit[j] = t2;

t = p[i];

p[i] = p[j];

p[j] = t;

t1 = w[i];

w[i] = w[j];

w[j] =t1;

}

}

}

}

float bound(float cp,float cw,int k)

{

float b = cp;

float c = cw;

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

{

c = c+w[i];

if( c < m)

b = b +p[i];

else

return (b+(1-(c-m)/ (float)w[i])*p[i]);

}

return b;

}

void knapsack(int k,float cp,float cw)

{

if(cw+w[k] <= m)

{

y[k] = 1;

if(k <= n)

knapsack(k+1,cp+p[k],cw+w[k]);

if(((cp+p[k]) > fp) && ( k == n))

{

fp = cp+p[k];

fw = cw+w[k];

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

x[j] = y[j];

}

}

if(bound(cp,cw,k) >= fp)

{

y[k] = 0;

if( k <= n)

knapsack(k+1,cp,cw);

if((cp > fp) && (k == n))

{

fp = cp;

fw = cw;

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

x[j] = y[j];

}

}

}

void main()

{

clrscr();

printf(“\n\n\n\t\t    ******** KNAPSACK PROBLEM ********”);

printf(“\n\t\t —————————————–”);

get();

printf(“\n The Sack is arranged in the order…\n”);

sort();

knapsack(0,0.0,0.0);

show();

getch();

}

Output:

******** KNAPSACK PROBLEM ********

——————————————-

Enter total number of items: 3

Enter the Maximum capacity of the Sack: 25

Enter the weight of the item # 1 : 1

Enter the profit of the item # 1 : 11

Enter the weight of the item # 2 : 11

Enter the profit of the item # 2 : 21

Enter the weight of the item # 3 : 21

Enter the profit of the item # 3 : 31

The Sack is arranged in the order…

Item    Weight     Cost    Unit Profit     Selected

1            1      11      11.000000          1

2            11     21      1.909091           0

3            21    31      1.476190           1

The Sack now holds following items : 1 3

Maximum Profit: 42.000000

Reference:

Computer Algorithms / C++ 2nd Edition by Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran

Implementation of Randomized Quick Sort


/* Randomized Quick Sort */

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int n;

void swap(int *a, int *b)

{

int x;

x = *a;

*a = *b;

*b = x;

}

void quicksort(int s[], int l, int h)

{

int p; /* index of partition */

if ((h – l) > 0) {

p = partition(s, l, h);

quicksort(s, l, p – 1);

quicksort(s, p + 1, h);

}

}

int partition(int s[], int l, int h)

{

int i;

int p; /* pivot element index */

int firsthigh; /* divider position for pivot element */

p = l + (random(n) % (h – l + 1));

swap(&s[p], &s[h]);

firsthigh = l;

for (i = l; i < h; i++)

if(s[i] < s[h]) {

swap(&s[i], &s[firsthigh]);

firsthigh++;

}

swap(&s[h], &s[firsthigh]);

 

return(firsthigh);

}

void main()

{

int s[20],i;

clrscr();

printf(“\nRandomized Quick Sort”);

printf(“\nEnter the no. of elements…”);

scanf(“%d”, &n);

printf(“\nEnter the elements one by one…”);

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

scanf(“%d”,&s[i]);

quicksort(s,0,n-1);

printf(“\nAfter sorting…\n”);

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

printf(“%d\t”,s[i]);

getch();

}

Follow

Get every new post delivered to your Inbox.

Join 71 other followers