arrays - 如何在二维数组中找到总和最大的元素？

Question

我需要找到具有最大总和的二维数组的元素。数组有 N 行和 13 列，其中行中元素的最大数量为 4，列中元素的数量必须为 2。我尝试在所有组合中使用迭代，但组合 (10^27) 比 Long 多.MAX_VALUE，当我尝试递归时，它导致了 stackoverflow。

可能的解决方案示例:

 _ _ _ _ _ _ _ _ _ _ _ _ _             _ _ _ _ _ _ _ _ _ _ _ _ _ 
|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 是该行前 6 列和后 7 列中元素的最大计数。我不知道用什么来找到它们。

Answer 1

您可以将其作为 max flow problem 来解决。

这个想法是，流代表从游泳者到学科的分配。

您可以在流量问题中分配容量以满足每个游泳者必须完成 2 个项目的约束，并且每个项目最多可以有 4 个游泳者，如下面的 Python 代码所示，它使用 NetworkX 库来解决最大流量问题。

import networkx as 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 is a discipline
# Each swimmer must do two disciplines
# At most 4 swimmers in any one discipline

num_swimmers = len(h)
num_disciplines = len(h[0])

G.add_node('dest',demand=num_swimmers*2)
A=[]
for i,costs in enumerate(h):
    name='swimmer%d'%i
    A.append(name)
    G.add_node(name,demand=-2) # 2 units of flow start at each swimmer 
    for discipline,cost in enumerate(costs):
        d='discipline%d'%discipline
        G.add_edge(name,d,capacity=1,weight=-cost)
for discipline in range(num_disciplines):
    d='discipline%d'%discipline
    G.add_edge(d,'dest',capacity=4,weight=0) # Can have at most 4 swimmers per discipline

flowdict = nx.min_cost_flow(G)
for swimmer in A:
    for d,flow in flowdict[swimmer].items():
        if flow:
            print swimmer,'->',d

print 'Total cost =',-nx.cost_of_flow(G,flowdict)

这会打印出答案:

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