algorithm - How to find elements in a 2 dimensional array with the biggest sum? -

i need find elements of 2 dimensional array maximal sum. array have n rows , 13 columns, maximal count of elements in row 4 , count of elements in column must 2. tried use iteration through combinations, there more combinations (10^27) long.max_value , when tried recursion caused stackoverflow.

examples of possible solutions:

 _ _ _ _ _ _ _ _ _ _ _ _ _             _ _ _ _ _ _ _ _ _ _ _ _ _  |x|x|x|x|_|_|_|_|_|_|_|_|_|m=4        |_|x|_|_|_|x|x|_|_|_|_|_|_| m=3 |x|x|x|x|_|_|_|_|_|_|_|_|_|m=4        |_|_|_|x|x|_|_|x|_|_|x|_|_| m=4 |_|_|_|_|x|x|x|x|_|_|_|_|_|m=4        |_|x|x|x|_|_|_|x|_|_|_|_|_| m=4 |_|_|_|_|x|x|x|x|_|_|_|_|_|m=4    or  |x|_|_|_|_|_|x|_|_|x|_|x|_| m=4 |_|_|_|_|_|_|_|_|x|x|x|_|x|m=4        |_|_|_|_|x|_|_|_|x|x|_|_|_| m=4 |_|_|_|_|_|_|_|_|x|x|x|x|_|m=4        |x|_|_|_|_|_|_|_|x|_|x|_|x| m=4 |_|_|_|_|_|_|_|_|_|_|_|x|x|m=4        |_|_|x|_|_|x|_|_|_|_|_|_|_| m=3                                       |_|_|_|_|_|_|_|_|_|_|_|x|x| m=2 

m maximal count of elemnts in first 6 columns , last 7 columns of row. haven't idea use find them.

you can solve max flow problem.

the idea flow represents assignment swimmer discipline.

you can assign capacities in flow problem in order satisfy constraints each swimmer must 2 disciplines, , each discipline can have @ 4 swimmers shown in python code below uses networkx library solve max flow problem.

import networkx nx  g=nx.digraph()  h = [[502,511,0,517,521,0,518,521,507,461,420,556,433,4],      [0,528,0,451,0 ,445,499,0,459,541,354,479,445, 4],      [0,524,488,419,0,458,579,0,0,490,565,473,428, 4],      [0,474,0,476,0,456,483,0,419,470,321,453,384,4],      [462,496,0,313,394,512,450,462,0,489,302,475,433,4],      [314,412,316,315,398,413,401,352,0,402,320,391,318,4],      [353,312,0,255,0,322,321,355,0,346,215,345,250,4]]  # each row discipline # each swimmer must 2 disciplines # @ 4 swimmers in 1 discipline  num_swimmers = len(h) num_disciplines = len(h[0])  g.add_node('dest',demand=num_swimmers*2) a=[] i,costs in enumerate(h):     name='swimmer%d'%i     a.append(name)     g.add_node(name,demand=-2) # 2 units of flow start @ each swimmer      discipline,cost in enumerate(costs):         d='discipline%d'%discipline         g.add_edge(name,d,capacity=1,weight=-cost) discipline in range(num_disciplines):     d='discipline%d'%discipline     g.add_edge(d,'dest',capacity=4,weight=0) # can have @ 4 swimmers per discipline  flowdict = nx.min_cost_flow(g) swimmer in a:     d,flow in flowdict[swimmer].items():         if flow:             print swimmer,'->',d  print 'total cost =',-nx.cost_of_flow(g,flowdict) 

this prints answer:

swimmer0 -> discipline4 swimmer0 -> discipline11 swimmer1 -> discipline1 swimmer1 -> discipline9 swimmer2 -> discipline6 swimmer2 -> discipline10 swimmer3 -> discipline6 swimmer3 -> discipline3 swimmer4 -> discipline5 swimmer4 -> discipline1 swimmer5 -> discipline5 swimmer5 -> discipline1 swimmer6 -> discipline7 swimmer6 -> discipline0 total cost = 6790