找到具有操作限制的最大总和

Question

作为输入，我得到了一个整数数组（全部为正数）。同样作为输入，我给出了一些“动作”。目标是找到具有给定操作数的数组元素的最大可能总和。作为一项“行动”，我可以：

将当前元素加到总和
移动到下一个元素

我们从数组中的 0 位置开始。每个元素只能添加一次。限制是：

2 < array.Length < 20
0 <“操作”数 < 20

在我看来，这种限制本质上并不重要。可以找到“动作”的每个组合，但在这种情况下，复杂性就像 2^“动作”，这很糟糕...))

例子:

array = [1, 4, 2], 3 actions.输出应为 5。在这种情况下，我们添加了零个元素，移动到第一个元素，添加了第一个元素。

array = [7, 8, 9], 2 actions.输出应该是 8。在这种情况下，我们移动到第一个元素，然后添加第一个元素。

谁能给我解释一下解决这个问题的算法？或者至少我应该尝试解决它的方向。

提前致谢

Answer 1

array = [1, 1, 1, 1, 100]
actions = 5

在上面的示例中，您只需要继续向右移动并最终拾取 100。在数组的开头，我们永远不知道接下来会看到什么值。所以，这不能贪心。

您有两个操作，您必须尝试两个操作，因为您不知道何时应用哪个。

下面是 python 代码。如果不熟悉，请将其视为伪代码或随意转换为您选择的语言。我们递归地尝试这两个动作，直到我们运行没有动作或者我们到达输入数组的末尾。

def getMaxSum(current_index, actions_left, current_sum):
    nonlocal max_sum
    if actions_left == 0 or current_index == len(array):
        max_sum = max(max_sum, current_sum)
        return 

    if actions_left == 1:
        #Add current element to sum
        getMaxSum(current_index, actions_left - 1, current_sum + array[current_index])
    else:
        #Add current element to sum and Move to the next element
        getMaxSum(current_index + 1, actions_left - 2, current_sum + array[current_index])

    #Move to the next element
    getMaxSum(current_index + 1, actions_left - 1, current_sum)
    
array = [7, 8, 9]
actions = 2
max_sum = 0

getMaxSum(0, actions, 0)
print(max_sum)

你会意识到这里可能存在重叠的子问题，我们可以通过 memoizing/caching 子问题的结果来避免那些重复的计算。我把这个任务留给你作为练习。基本上，这是动态规划问题。

希望对您有所帮助。 Post 如有疑问，请在评论中提出。

Answer 2

这是另一个使用记忆的 DP 解决方案。这个想法是用一对整数 (current_index, actions_left) 表示状态，并将其映射到从 current_index 开始时的最大总和，假设 actions_left 是我们允许的动作的上限采取：

from functools import lru_cache

def best_sum(arr, num_actions):
  'get best sum from arr given a budget of actions limited to num_actions'

  @lru_cache(None)
  def dp(idx, num_actions_):
    'return best sum starting at idx (inclusive)'
    'with number of actions = num_actions_ available'
    # return zero if out of list elements or actions
    if idx >= len(arr) or num_actions_ <= 0:
      return 0
    # otherwise, decide if we should include current element or not
    return max(
        # if we include element at idx
        # we spend two actions: one to include the element and one to move 
        # to the next element
        dp(idx + 1, num_actions_ - 2) + arr[idx],
        # if we do not include element at idx
        # we spend one action to move to the next element
        dp(idx + 1, num_actions_ - 1)
        )
  
  return dp(0, num_actions)

我正在使用 Python 3.7.12.

找到具有操作限制的最大总和

Finding max sum with operation limit

arrays

algorithm

sum

max