Talk:Stable marriage problem: Difference between revisions
Content added Content deleted
(→Test) |
|||
Line 9: | Line 9: | ||
::This bring up old memories from those classes in national economy, where one thing was how to calculate the maximum sum of ‘usefulness’ that any resource could do in a society. And that is neither “all to one”, or “equal to all”. Resources where according o the maximization thesis to be spread so that their total sum is maximized, e.g. alls individual needs for different resources valued against their specific needs and available resources… I think I just connected it into the Knapsack series… --[[User:Jofur|<Jofur>]] 12:59, 6 August 2010 (UTC) |
::This bring up old memories from those classes in national economy, where one thing was how to calculate the maximum sum of ‘usefulness’ that any resource could do in a society. And that is neither “all to one”, or “equal to all”. Resources where according o the maximization thesis to be spread so that their total sum is maximized, e.g. alls individual needs for different resources valued against their specific needs and available resources… I think I just connected it into the Knapsack series… --[[User:Jofur|<Jofur>]] 12:59, 6 August 2010 (UTC) |
||
==Test== |
|||
Just found [http://www.spoj.pl/problems/STABLEMP/ this site] which has two testcases and expected results. I modified the Python solution: |
|||
<lang python> |
|||
if True: |
|||
## Sphere online judge dataset from: http://www.spoj.pl/problems/STABLEMP/ |
|||
## (But they print couples in reversed order) |
|||
galprefers = dict( (x.strip().split()[0], x.strip().split()[1:]) |
|||
for x in ''' 1 3 4 2 1 6 7 5 |
|||
2 6 4 2 3 5 1 7 |
|||
3 6 3 5 7 2 4 1 |
|||
4 1 6 3 2 4 7 5 |
|||
5 1 6 5 3 4 7 2 |
|||
6 1 7 3 4 5 6 2 |
|||
7 5 6 2 4 3 7 1'''.split('\n') ) |
|||
guyprefers = dict( (x.strip().split()[0], x.strip().split()[1:]) |
|||
for x in ''' 1 4 5 3 7 2 6 1 |
|||
2 5 6 4 7 3 2 1 |
|||
3 1 6 5 4 3 7 2 |
|||
4 3 5 6 7 2 4 1 |
|||
5 1 7 6 4 3 5 2 |
|||
6 6 3 7 5 2 4 1 |
|||
7 1 7 4 2 6 5 3'''.split('\n') ) |
|||
guys = sorted(guyprefers.keys()) |
|||
gals = sorted(galprefers.keys()) |
|||
</lang> |
|||
Which then went on to provide the correct result. (I was relying on the check() function before. --[[User:Paddy3118|Paddy3118]] 14:04, 6 August 2010 (UTC) |