作為輸入，我得到一個整數陣列（均為正數）。同樣作為輸入，我得到了許多“動作”。目標是找到具有給定數量的動作的陣列元素的最大可能總和。作為“行動”，我可以：
- 將當前元素添加到總和
- 移動到下一個元素
我們從陣列中的 0 位置開始。每個元素只能添加一次。限制是：
- 2 < 陣列長度 < 20
- 0 < “動作”數 < 20
在我看來，這種限制本質上并不重要。它可以找到“動作”的每個組合，但在這種情況下，復雜性就像 2^“動作”，這很糟糕......））
例子：
陣列 = [1, 4, 2] , 3 個動作。輸出應該是 5。在這種情況下，我們添加零元素，移動到第一個元素，添加第一個元素。
陣列 = [7, 8, 9] , 2 個動作。輸出應該是 8。在這種情況下，我們移動到第一個元素，然后添加第一個元素。
誰能解釋一下解決這個問題的演算法？或者至少是我應該嘗試解決它的方向。
提前致謝
uj5u.com熱心網友回復：
這是另一個使用 memoization 的 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 to 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 indclude element at idx
# we spend one action to move to the next element
dp(idx 1, num_actions_ - 1)
)
return dp(0, num_actions)
我的解決方案不同意該執行緒中的所有答案。例如，
lst = [2, 2, 2, 1, 5]
assert best_sum(lst, 5) == 6
# actions: keep, move, keep, move, keep
assert sum(getMaxSum(lst, 5)) == 5
我正在使用 Python 3.7.12。
uj5u.com熱心網友回復：
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)
您會意識到這里可能存在重疊的子問題，我們可以通過將結果記憶/快取到子問題來避免那些重復的計算。我把這個任務留給你作為練習。基本上，這是動態規劃問題。
希望它有所幫助。如有任何疑問，請在評論中發表。
uj5u.com熱心網友回復：
確實有貪心的解決方案，這里不需要DP。
有了n行動預算，如果我們取x數字，我們最多可以達到n-x-1第 th 個數字。常識：只取最高的數字是有意義的。解決方案：迭代到n-1第 th 個數，維護一個 top x 的堆。
def getMaxSum(data, action_budget=None):
action_budget = action_budget or len(data)
start_idx = (action_budget 1) // 2
heap = data[:start_idx]
heapq.heapify(heap)
best_heap = heap.copy()
best_sum = sum(heap)
for position in range(start_idx, min(action_budget, len(data))):
new_sum = best_sum data[position]
heapq.heappush(heap, data[position])
while len(heap) > action_budget - position:
new_sum -= heapq.heappop(heap)
if new_sum > best_sum:
best_sum = new_sum
best_heap = heap.copy()
return best_heap
總體復雜度為 O(n log n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/406612.html
標籤：
上一篇：這是什么數學系列，方程式是什么？
下一篇：無法將類語法轉換為鏈表的函式語法