#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int dim,arr[5][5];
int curr_best[6]={-1,-1,-1,-1,-1,-1},x[5]={-1,-1,-1,-1};
void estimate(int,int,int[4]);
void build(int);
// x[k] will contain the choices till now for the current series
// the best soln till now is in curr_best[last] has the value
int main()
{
int i,j;
//clrscr();
printf("\n\n\t\t Please Enter the dimension of array : ");
scanf("%d",&dim);
printf("\n\n\t\t Please Enter the array \n");
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
printf("\n\t Please Enter [%d][%d] : ",i,j);
scanf("%d",&arr[i][j]);
}
}
//
//clrscr();
build(0);
printf("\n\n\n\t\t\t FINAL SOLUTION IS\n\n");
for(i=0;i<dim;i++)
printf("\n\t\t [%d][%d] = %d",i,curr_best[i],arr[i][curr_best[i]]);
printf("\n\n\t\t TOTAL COST = %d\n\n\n",curr_best[dim]);
getch();
}
void build(int k)
{
int i,j,temp,update=0;
int flag,value[5]={0,0,0,0,0};
//represents the estimates if the index of next k is the index of this
array
int explored[5]={0,0,0,0,0}; // flag =1 means explored so actual value
// else estimate
for(i=k;i<dim;i++)
x[i]=-1;
//update the value[] to till now
if(k>0)
for(i=0;i<k;i++)
update+=arr[i][x[i]];
for(i=0;i<dim;i++) //column --- checking if i is valid or not
{
flag=0;
for(j=0;j<k;j++)
{
if(x[j]==i) // check if something is fixed to this column
{
flag=1;
break;
}
}
if(flag==0) // means i qualifies
{
value[i]+=arr[k][i]+update;
printf("\n\n\n\t\t\tFixing [%d][%d] = %d\n",k,i,arr[k][i]);
getch();
x[k]=i;
estimate(i,k+1,value);
}
}
for(i=0;i<dim;i++)
{
if(value[i]!=0)
printf("\n\n\t Estimate for [%d][%d] = %d",k,i,value[i]);
getch();
}
// before calling build again update explored
// do not see explored contents again once u return
// update curr_best when u finish a series
// upon returning, check the choices left (unexplored) values if any
is better
// than curr_best
while(1)
{
temp=-1;
for(i=0;i<dim;i++)
{
if(value[i]!=0 && explored[i]==0)
{
if(value[i]<value[temp] || temp==-1)
{
temp=i;
}
}
}
if(temp==-1)
break;
if(value[temp]<curr_best[dim] || curr_best[dim]==-1)
{
printf("\n\n\t\t\tExploring for [%d][%d] ",k,temp);
getch();
explored[temp]=1;
x[k]=temp;
if(k<dim-1)
build(k+1);
else
{
for(j=0;j<dim;j++)
curr_best[j]=x[j];
curr_best[dim]=value[temp];
break;
}
}
else
break;
}
}
void estimate(int pos,int k,int value[5])
{
int i,j,l,temp=-1,flag=0;
// k gives the row (earlier ones to be ignored)
for(i=k;i<dim;i++)
x[i]=-1;
for(i=0;i<dim;i++) //column --- checking if i is valid or not
{
flag=0;
for(j=0;j<dim;j++)
{
if(x[j]==i) // check if something is fixed to this column
{
flag=1;
break;
}
}
if(flag==0) // means i qualifies
{
temp=-1;
for(l=k;l<dim;l++) // rows
{
printf("\n\t Comparing [%d][%d] = %d",l,i,arr[l][i]);
getch();
if(temp==-1 || temp>arr[l][i])
{
temp=arr[l][i];
}
}
printf("\n\n\t\t Selecting %d\n",temp);
getch();
value[pos]+=temp;
}
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
