Re: [algogeeks] help to give DP solution

2012-09-17 Thread Tushar 
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 
> > 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 
>> 
>> > 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 
>>> Patle
>>> M.Tech, School of Information Technology
>>> Indian Institute of Technology, Kharagpur-721302, 
>>> India
>>> Mobile No: +91-8798049298, +91-9424738542
>>> Alternate Email: rahulku...@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 algo...@googlegroups.com
>>> .
>>> To unsubscribe from this group, send email to 
>>> algogeeks+...@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 algo...@googlegroups.com
>> .
>> To unsubscribe from this group, send email to 
>> algogeeks+...@googlegroups.com .
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> -- 
> Thanks and Regards:
> Rahul Kumar 
> Patle
> M.Tech, School of Information Technology
> Indian Institute of Technology, Kharagpur-721302, 
> India
> Mobile No: +91-8798049298, +91-9424738542
> Alternate Email: rahulku...@hotmail.com 
>
>

-- 
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

2012-09-16 Thread atul anand 
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  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 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 <
>>> 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 
 Patle
 M.Tech, School of Information Technology
 Indian Institute of Technology, Kharagpur-721302, 
 India
 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 
>> Patle
>> M.Tech, School of Information Technology
>> Indian Institute of Technology, Kharagpur-721302, 
>> India
>> 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

2012-09-16 Thread atul anand 
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 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 <
>> 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 
>>> Patle
>>> M.Tech, School of Information Technology
>>> Indian Institute of Technology, Kharagpur-721302, 
>>> India
>>> 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 
> Patle
> M.Tech, School of Information Technology
> Indian Institute of Technology, Kharagpur-721302, 
> India
> 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

2012-09-16 Thread Rahul Kumar Patle 
@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 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 <
> 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 
>> Patle
>> M.Tech, School of Information Technology
>> Indian Institute of Technology, Kharagpur-721302, 
>> India
>> 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 Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
India
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

2012-09-16 Thread atul anand 
@tushar :- correct...

On Sun, Sep 16, 2012 at 12:59 PM, Tushar  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

2012-09-16 Thread Tushar 
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

2012-09-15 Thread Ravi Ranjan 
@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.

Re: [algogeeks] help to give DP solution

2012-09-15 Thread atul anand 
typo error :-
and each *row* *as cost

On Sun, Sep 16, 2012 at 12:44 AM, atul anand 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 <
> 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 
>> Patle
>> M.Tech, School of Information Technology
>> Indian Institute of Technology, Kharagpur-721302, 
>> India
>> 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

2012-09-15 Thread atul anand 
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 
> Patle
> M.Tech, School of Information Technology
> Indian Institute of Technology, Kharagpur-721302, 
> India
> 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

2012-09-15 Thread Rahul Kumar Patle 
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 Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
India
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.