我撰寫了這段代碼，用于將陣列 S 拆分為 k 個連續段，以最小化這 k 個段中的最大總和。這里 S 是一個序列，所以我不能改變元素的順序。這是代碼：
def Opt(i, j):
n = len(i)
sum = [0]*(n 1)
dp = [[0 for a in range(n 1)] for a in range(2)]
for a in range(0,n):
sum[a 1] = i[a] sum[a]
dp[0][a 1] = float('inf')
dp[1][a 1] = float('inf')
for a in range(1,j 1):
for b in range(1,n 1):
for c in range(a-1,b):
dp[a%2][b] = min(dp[a%2][b], max(dp[(a-1)%2][c], sum[b]-sum[c]))
return dp[j%2][n]
# Driver Code
if __name__ == '__main__':
S = [7,2,5,10,8]
k = 2
M = sum(S)/len(S)
ans = Opt(S,k)
print(ans)
這作業得很好。但我也想回傳我計算了最小最大總和的段。例如，對于陣列S = [3,3,7,33]，k=3此演算法回傳答案“33”，但我想將段回傳為[[3,3],[7],[33]]. 但我無法做到。有誰能夠幫我？
uj5u.com熱心網友回復：
您需要使用追溯技術（不確定該名稱是否被廣泛使用，或者只是在生物資訊學中）。
當您為每個子問題填寫動態規劃矩陣時，您還填寫了一個回溯矩陣，該矩陣對每個子問題的解決方案進行編碼。
對于您的問題，回溯可以存盤子陣列的最佳斷點：
def Opt(i, j):
n = len(i)
sum = [0]*(n 1)
dp = [[0 for a in range(n 1)] for a in range(2)]
tb = [[[] for a in range(n 1)] for a in range(2)]
for a in range(0,n):
sum[a 1] = i[a] sum[a]
dp[0][a 1] = float('inf')
dp[1][a 1] = float('inf')
for a in range(1,j 1):
for b in range(a 1,n 1):
for c in range(a - 1, b):
# if c should be a breakpoint, then...
if max(dp[(a-1)%2][c], sum[b]-sum[c]) < dp[a%2][b]:
# ...update the best score, and...
dp[a%2][b] = max(dp[(a-1)%2][c], sum[b]-sum[c])
# ...update the solution
tb[a%2][b] = tb[(a - 1)%2][c] [c]
# extract optimal sub-arrays
starts = tb[j%2][n]
ends = starts[1:] [n]
sub_arrays = [i[s:e] for s, e in zip(starts, ends)]
return sub_arrays
S = [7,2,5,10,8]
Opt(S, 2) # ==> [[7, 2, 5], [10, 8]]
Opt(S, 3) # ==> [[7, 2, 5], [10], [8]]
Opt([3, 7, 7, 33], 3) # ==> [[3, 7], [7], [33]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422808.html
標籤：