[algogeeks] efficient backtracking algorithm for the coin changing problem
Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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.
[algogeeks] Re: Divide and Conquer problem
Thnx guys for the help.. On Apr 7, 7:45 pm, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Following are the recurrences: T(n)=2T(n/2)+1 T(2)=1 T(n)=n-1 =O(n) 1 is added because winner of both the sides will compete at most 1 once. for Time table u can form a tree x1 x2 x3 x4 x5 \ / \ / / x1 x3 / \ \ / \ x5 \ / x1 Here are four matches and team nos =5 On Wed, Apr 7, 2010 at 12:20 PM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Can any one help me with this problem Its a divide and conquer problem where, there are n teams and each team plays each opponent only once. And each team plays exactly once every day. If n is the power of 2, I need to construct a timetable allowing the tournament to finish in n-1 days... Any help would be appreciated.. thanks -- 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.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.com -- 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.
[algogeeks] branch and bound algorithm for TSP problem..
I want some help to implement branch and bound algorithm for the TSP problem... I got the many leads for TSP problem but none of them were in Branch and Bound method... Will appreciate any help... thanks guys -- 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.
[algogeeks] Branch and Bound version for TSP.. hope it helps u guys.....
#includestdio.h
#includeconio.h
#includestdlib.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;idim;i++)
{
for(j=0;jdim;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;idim;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;idim;i++)
x[i]=-1;
//update the value[] to till now
if(k0)
for(i=0;ik;i++)
update+=arr[i][x[i]];
for(i=0;idim;i++) //column --- checking if i is valid or not
{
flag=0;
for(j=0;jk;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;idim;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;idim;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(kdim-1)
build(k+1);
else
{
for(j=0;jdim;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;idim;i++)
x[i]=-1;
for(i=0;idim;i++) //column --- checking if i is valid or not
{
flag=0;
for(j=0;jdim;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;ldim;l++) // rows
{
printf(\n\t Comparing [%d][%d] = %d,l,i,arr[l][i]);
getch();
if(temp==-1 || temparr[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.
[algogeeks] Divide and Conquer problem
Can any one help me with this problem Its a divide and conquer problem where, there are n teams and each team plays each opponent only once. And each team plays exactly once every day. If n is the power of 2, I need to construct a timetable allowing the tournament to finish in n-1 days... Any help would be appreciated.. thanks -- 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.
