#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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.