Re: [algogeeks] help to give DP solution
www.ams.jhu.edu/~castello/362/Handouts/*hungarian*.pdf This PDF might be helpful On Sunday, 16 September 2012 16:42:25 UTC+5:30, Rahul Kumar Patle wrote: @atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.8...@gmail.comjavascript: wrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlera...@gmail.comjavascript: wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulku...@hotmail.com javascript: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulku...@hotmail.com javascript: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/p2mOfKSQbrUJ. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
we can assign minimum possible value, like negative infinity to the diagonal elements. Then they would not be considered for maximizing the sum. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/iQtl7QGJBFwJ. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
@tushar :- correct... On Sun, Sep 16, 2012 at 12:59 PM, Tushar tushicom...@gmail.com wrote: we can assign minimum possible value, like negative infinity to the diagonal elements. Then they would not be considered for maximizing the sum. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/iQtl7QGJBFwJ. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
@atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
make all mat[i][j] to -ve sign and make mat[i][j]=INT_MAX now i guess same algo will work..no changes required. On Sun, Sep 16, 2012 at 4:42 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
typo error :- mat[ i ] [ j ] to -ve sign and make mat[ i ][ i ]=INT_MAX On Mon, Sep 17, 2012 at 9:43 AM, atul anand atul.87fri...@gmail.com wrote: make all mat[i][j] to -ve sign and make mat[i][j]=INT_MAX now i guess same algo will work..no changes required. On Sun, Sep 16, 2012 at 4:42 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] help to give DP solution
A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
typo error :- and each *row* *as cost On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] help to give DP solution
@atul agreed with u dat it can be solved through hungarian method.. but what about the condition a[i][i] entry is invalid if all elements lie on diagonal n d sum is also maximum den a[i][i] condition will be violated but Hungarian method still works -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
