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

}

Introduction to Heap


What is a heap?

A heap is a partially sorted binary tree. Although a heap is not completely in order, it conforms to a sorting principle: every node has a value less (for the sake of simplicity, we will assume that all orderings are from least to greatest) than either of its children. Additionally, a heap is a “complete tree” — a complete tree is one in which there are no gaps between leaves. For instance, a tree with a root node that has only one child must have its child as the left node. More precisely, a complete tree is one that has every level filled in before adding a node to the next level, and one that has the nodes in a given level filled in from left to right, with no breaks.

Why use a heap?

Continue reading

Stack Class With Exception Handling


//Stack Operations with Exception Handling

Note: To execute this program use any one of the ANSI C++ Compiler (GCC for Linux, Borland C++)

Borland C++

Free C/C++ Compilers

Free C++ Programming Tools

Free ANSI C++ for Windows

Program

#include<iostream>

#include<iomanip>

#include<process>

using namespace std;

class stack

{

private:

int *s;

int max;

int top;

public:

class FULL{};  //for exception handling

class EMPTY{}; //for exception handling

stack(int);

void push(int);

int pop(void);

void display(void);

};

stack::stack(int m)

{

s=new int[m];

top=-1;

max=m;

}

void stack::push(int item)

{

if(top<max-1)

s[++top]=item;

else

throw FULL(); //FULL object is thrown

}

int stack::pop(void)

{

if(top>=0)

return s[top–];

else

throw EMPTY(); //EMPTY object is thrown

}

void stack::display(void)

{

if(top>=0)

for(int i=top; i>=0;i–)

cout<<“\n\t|”<<setw(4)<<s[i]<<“|\n\t——“;

else

throw EMPTY();

}

int main()

{

int item, size;

int ch=1;

cout<<“\nEnter the size of stack…”;

cin>>size;

stack s1(size);

cout<<“\nStack with Exception Handling”;

cout<<“\n\n\tMENU\n1.PUSH\n2.POP\n3.SHOW STACK\n4.EXIT”;

cout<<“\nEnter your choice…”;

cin>>ch;

do

{

switch(ch)

{

case 1:

cout<<“\nEnter the item to push…”;

cin>>item;

try

{

s1.push(item);

}

catch(stack::FULL)  //FULL object is caught

{

cout<<“\n***Stack Overflow***\n”;

}

break;

case 2:

try

{

cout<<“\nPoped Item is…”<<s1.pop();

}

catch(stack::EMPTY) //EMPTY object caught

{

cout<<“\n***Stack Empty***\n”;

}

break;

case 3:

cout<<“\nThe Stack is…\n”;

try

{       s1.display();    }

catch(stack::EMPTY)

{

cout<<“\n***Stack Empty***\n”;

}

break;

case 4:

exit(0);

}

cout<<“\nEnter your choice…”;

cin>>ch;

}while(ch<5);

return 0;

}

Circular Linked List – Model 2


/*Circular Linked List*/

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void insert(int a,int b);
void dis();
void search(int c);
void del(int d);
void len();
void empty();
int l=0,f=0;
struct list
{
int data;
struct list *link;
}*first,*cir;
void dis()
{
struct list *cu;
for(cu=first;cu->link!=cir->link;cu=cu->link)
{
printf(“%d”,cu->data);
if(cu->link!=cir)
printf(“->”);
}
}
void len()
{
struct list *cur;
for(cur=first;cur->link!=cir->link;cur=cur->link)
{
l++;
}
printf(“\n The size of the list is:%d\n”,l);
}
void empty()
{
if(first==0)
{
printf(“\n The List is empty”);
}
else
{
printf(“The list is not empty\n”);
}
}
void search(int g)
{
struct list *p=first;
for(p=first;p->link!=cir->link;p=p->link)
{
if(p->data==g)
{
printf(“\n The element is Present\n”);
f=0;
break;
}
else
{
f=1;
}
}
if(f==1)
{
printf(“\n Element is not present\n”);
}
}
void del(int u)
{
int i;
struct list *cu=first,*q=first;
for(i=1;i<u;i++)
cu=cu->link;
for(i=1;i<=u;i++)
q=q->link;
if(u)
{
cu->link=q->link;
delete(q);
}
else if(cu->link!=NULL && q->link==cir->link)
{
cu->link=cir;
delete(q);
}
if(u==0)
{
first=q->link;
cir->link=first;
delete(q);
}
}
void insert(int a,int b)
{
int i;
struct list *p=first,*q;
q=(struct list*)malloc(sizeof(struct list*));
for(i=1;i<a;i++)
{
p=p->link;
}
q->data=b;
if(a)
{
q->link=p->link;
p->link=q;
}
else
{
q->link=cir;
//first->link=cir;
cir->link=first;
first=q;
}
}
void main()
{
first=(struct list*)malloc(sizeof(struct list*));
cir=(struct list*)malloc(sizeof(struct list*));
first=NULL;
//cir=0;
int c,p,v,s,d;
clrscr();
do
{
printf(“\n Enter your Choice:\n”);
printf(“1.Insert\n2.Delete\n3.display\n4.search\n5.Lenth\n6.Empty\n7.Exit\n”);
scanf(“%d”,&c);
switch(c)
{
case 5:
len();
break;
case 6:
empty();
break;
case 1:
printf(“\n Enter the position and value:\n”);
scanf(“%d%d”,&p,&v);
insert(p,v);
break;
case 2:
printf(“\nenter the position to delete:\n”);
scanf(“%d”,&d);
del(d);
break;
case 3:
printf(“\n The Elements are:\n”);
dis();
break;
case 4:
printf(“\n Enter the element to search:\n”);
scanf(“%d”,&s);
search(s);
break;
default:
printf(“\n Exit Choice\n”);
}
}while(c!=7);
getch();
}

Implementation of Circular Linked List


/* Circular linked list*/

# include<stdio.h>
# include<conio.h>
# include<alloc.h>
# include<stdlib.h>

struct node
{
int data;
struct node *link;
};
void append(struct node **,int);
void in_begin(struct node **,int);
void del(struct node **,int);
void in_middle(struct node **,int,int);
int count(struct node *);
void next(struct node **,int);
void display(struct node *);
struct node *last=NULL;

void main()
{
struct node *p=NULL;/* p can be said as the head or a start ptr */
int num,loc;
char choice;
char ans;
do
{
clrscr();
printf(“PROGRAM TO IMPLEMENT SINGLY LINKED LIST “);
printf(“\n=====================================”);
printf(“\n\n1.Create \\ Appending The List”);
printf(“\n2.Insert Node At Begining”);
printf(“\n3.Insert Node In Middle”);
printf(“\n4.Deleting a  Node”);
printf(“\n5.Counting The No Of Nodes”);
printf(“\n6.Next”);
printf(“\n7.Displaying the list”);
printf(“\n8.Exit”);
oper:
printf(“\n\nEnter ur Choice : “);
fflush(stdin);
scanf(“%c”,&choice);
switch(choice)
{
case ‘1’:
do
{
printf(“Enter any number : “);
scanf(“%d”,&num);
append(&p,num);
printf(“Enter more (y/n) :”);
fflush(stdin);
ans=getchar();
}while(ans !=’n’);
break;
case ‘2’:
printf(“Enter The Data : “);
scanf(“%d”,&num);
in_begin(&p,num);
break;
case ‘3’:
printf(“\nEnter The Position :”);
scanf(“%d”,&loc);
printf(“\nEnter The Data : “);
scanf(“%d”,&num);
in_middle(&p,loc,num);
break;
case ‘4’:
printf(“\nEnter The Data u Want To Delete : “);
scanf(“%d”,&num);
del(&p,num);
break;
case ‘5’:
printf(“\nThe No Of Nodes Are %d”,count(p));
getch();
break;
case ‘6’:
printf(“\nEnter a number:”);
scanf(“%d”,&num);
next(&p,num);
getch();
break;
case ‘7’:
display(p);
getch();
break;
case ‘8’:
printf(“\n\nQuiting…….”);
getch();
exit(0);
break;
default:
printf(“Invalid choice.Please Enter Correct Choice”);
getch();
goto oper;
}
}while(choice !=7);
}
void next(struct node **q,int num)
{
struct node *temp=*q;
if(temp==NULL)
{
printf(“\nEmpty list.”);
return;
}
while(temp!=last && temp->data!=num)
temp=temp->link;
if(temp==last)
{
if(temp->data==num)
printf(“The next element is %d”,(*q)->data);
else
printf(“The given element is not in the list.”);
}
else
printf(“The next element is %d.”,temp->link->data);
}
void append(struct node **q,int num)
{
struct node *temp,*r,*f;
temp = *q;
f=temp;
if(*q==NULL)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->data=num;
temp->link=temp;
*q=temp;
last=temp;
}
else
{
temp = *q;
if(temp==last)//only 1 node
goto l;
while(temp->link !=f)
{
temp=temp->link;
}
l:
r = (struct node *)malloc(sizeof(struct node));
r->data=num;
r->link=f;
temp->link=r;
last=r;
}
}

void display(struct node *q)
{
if(q==NULL)
{
printf(“\n\nEmpty Linked List.Can’t Display The Data”);
goto last;
}
if(q==last)
printf(“\n%d–>”,q->data);
else
{
printf(“\n”);
while(q!=last)
{
printf(“%d–>”,q->data);
q=q->link;
}
printf(“%d”,q->data);
}
last:
}

int count(struct node *q)
{
int c=0;
if(q==NULL)
{
printf(“Empty Link List.\n”);
getch();
goto last;
}
while(q!=last)
{
c++;
q=q->link;
}
c++;
last:
return c;

}

void in_begin(struct node **q,int num)
{
struct node *temp;
if(*q==NULL)
{
printf(“Link List Is Empty.Can’t Insert.”);
getch();
goto last;
}
else
{
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
temp->link=*q;
*q=temp;  /* pointing to the first node */
last->link=temp;
}
last:
printf(“\nInserted.”);
getch();
}

void in_middle(struct node **q,int loc,int num)
{
struct node *temp,*n;
int c=1,flag=0;
temp=*q;
if(*q==NULL)
{
printf(“\n\nLink List Is Empty.Can’t Insert.”);
getch();
goto last;
}
else
while(temp!=last)
{
if(c==loc)
{
n = (struct node *)malloc(sizeof(struct node));
n->data=num;
n->link=temp->link;
temp->link=n;
flag=1;
}
c++;
temp=temp->link;
}
if(flag==0)
{
printf(“\n\nNode Specified Doesn’t Exist.Cant Enter The Data”);
getch();
}
else
{
printf(“Data Inserted”);
getch();
}
last:
getch();
}

void del(struct node**q,int num)
{
if(*q==NULL)
{
printf(“\n\nEmpty Linked List.Cant Delete The Data.”);
getch();
}
else if(*q==last && (*q)->data==num)
{
free(last);
*q=last=NULL;
printf(“\nData deleted.”);
}
else
{
struct node *old,*temp;
int flag=0;
temp=*q;
while(temp!=last)
{
if(temp->data==num)
{
if(temp==*q)         /* First Node case */
{
*q=temp->link;  /* shifted the header node */
last->link=*q;
}
else if(temp==last)
{
old->link=*q;
last=old;
}
else
old->link=temp->link;
free(temp);
flag=1;
break;
}
else
{
old=temp;
temp=temp->link;
}
}
if(flag==0)
printf(“\nData Not Found…”);
else
printf(“\nData Deleted.”);
}
getch();
}

Follow

Get every new post delivered to your Inbox.

Join 82 other followers