矩阵中k个连续元素的最大和

Question

给定一个正整数值的网格和一个整数K，最大的连续元素和是多少？

这里有一个5x5矩阵的例子，K值为6。

有人能帮我识别这个问题吗？我该如何开始解决它？
我知道的唯一方法是对该矩阵的每个单元格进行深度优先搜索。但我认为这不是最好的方法。

不允许重复的单元格。

这里的连接仅意味着一个单元格与另一个单元格水平或垂直相邻

- Felipe

---

我不确定这个问题是否适合在这里提问... - Thomas Ayoub

嗯...可以建模为图论问题：在该矩阵的连接图中找到一个大小为K的子图。 - fuz

听起来有点像收集奖品的斯坦纳问题。 - fuz

这篇论文描述了你的问题的图论变体（他们称其为预算版本的奖励收集斯坦纳问题），并列举了可能的解决策略。 - fuz

如果你无法解决一个问题，尝试解决一个更简单的问题。这个Project Euler问题（在矩阵中向上下和右移动的最大路径）可能会帮助你思考：https://projecteuler.net/problem=82 - Colonel Panic

你的问题更难，因为它允许任何连接的子集，而不仅仅是路径（如你的图片所示）。并非所有连接的子集都是路径（考虑T形状）。我建议从将Project Euler问题从三方向路径推广到四方向路径开始尝试。 - Colonel Panic

Answer 1

我想你可以漫步并在此过程中进行备忘录记忆。我使用镜像位集来表示备忘的路径，以便无论从哪个方向构建都能立即识别。这里是Python版本（哈希长度包括从大小为一到六的路径计数）：

from sets import Set

def f(a,k):
  stack = []
  hash = Set([])
  best = (0,0) # sum, path
  n = len(a)

  for y in range(n):
    for x in range(n):
      stack.append((1 << (n * y + x),y,x,a[y][x],1))

  while len(stack) > 0:
    (path,y,x,s,l) = stack.pop()

    if l == k and path not in hash:
      hash.add(path)
      if s > best[0]:
        best = (s,path)
    elif path not in hash:
      hash.add(path)
      if y < n - 1:
        stack.append((path | (1 << (n * (y + 1) + x)),y + 1,x,s + a[y + 1][x],l + 1))
      if y > 0:
        stack.append((path | (1 << (n * (y - 1) + x)),y - 1,x,s + a[y - 1][x],l + 1))
      if x < n - 1:
        stack.append((path | (1 << (n * y + x + 1)),y,x + 1,s + a[y][x + 1],l + 1))
      if x > 0:
        stack.append((path | (1 << (n * y + x - 1)),y,x - 1,s + a[y][x - 1],l + 1))

  print best
  print len(hash)

输出：

arr = [[31,12,7,1,14]
      ,[23,98,3,87,1]
      ,[5,31,8,2,99]
      ,[12,3,42,17,88]
      ,[120,2,7,5,7]]

f(arr,6) 

""" 
(377, 549312) sum, path
1042 hash length
549312 = 00000
         01110
         11000
         10000 
"""

更新：这个问题与如何在矩阵中找到M个相邻元素的最大总和类似，我意识到需要对我的建议进行修订，以包括从形状中间部分延伸的形态。以下是我修改后的代码，使用集合来哈希形状。在我看来，DFS应该能够使堆栈大小保持在O(m)的数量级（尽管搜索空间仍然很大）。

from sets import Set

def f(a,m):
  stack = []
  hash = Set([])
  best = (0,[]) # sum, shape
  n = len(a)

  for y in range(n):
    for x in range(n):
      stack.append((a[y][x],Set([(y,x)]),1))

  while len(stack) > 0:
    s,shape,l = stack.pop()

    key = str(sorted(list(shape)))

    if l == m and key not in hash:
      hash.add(key)
      if s > best[0]:
        best = (s,shape)
    elif key not in hash:
      hash.add(key)
      for (y,x) in shape:
        if y < n - 1 and (y + 1,x) not in shape:
          copy = Set(shape)
          copy.add((y + 1,x))
          stack.append((s + a[y + 1][x],copy,l + 1))
        if y > 0 and (y - 1,x) not in shape:
          copy = Set(shape)
          copy.add((y - 1,x))
          stack.append((s + a[y - 1][x],copy,l + 1))
        if x < n - 1 and (y,x + 1) not in shape:
          copy = Set(shape)
          copy.add((y,x + 1))
          stack.append((s + a[y][x + 1],copy,l + 1))
        if x > 0 and (y,x - 1) not in shape:
          copy = Set(shape)
          copy.add((y,x - 1))
          stack.append((s + a[y][x - 1],copy,l + 1))

  print best
  print len(hash)

输出：

arr = [[31,12,7,1,14]
      ,[23,98,3,87,1]
      ,[5,31,8,2,99]
      ,[12,3,42,17,88]
      ,[120,2,7,5,7]]

f(arr,6)

"""
(377, Set([(1, 2), (1, 3), (1, 1), (2, 3), (3, 4), (2, 4)]))
2394 hash length
"""

- גלעד ברקן