問題陳述：
我們得到了三個A1,A2,A3長度陣列n1,n2,n3。每個陣列包含一些（或沒有）自然數（即> 0）。這些數字表示程式執行時間。
任務是從任何陣列中選擇第一個元素，然后您可以執行該程式并將其從該陣列中洗掉。
例如：
if A1=[3,2] (n1=2),
A2=[7] (n2=1),
A3=[1] (n3=1)
然后我們可以按各種順序執行程式，例如[1,7,3,2]or [7,1,3,2]or [3,7,1,2]or or [3,1,7,2]or [3,2,1,7]etc.
現在，如果我們將S=[1,3,2,7]執行順序作為各種程式的等待時間，則
S[0] 等待時間 = 0，因為立即執行，
S[1] 等待時間 = 0 1 = 1，考慮到以前的時間，同樣，
對于 S[ 2] 等待時間 =0 1 3 = 4
對于 S[3] 等待時間 =0 1 3 2 = 6
現在陣列的分數定義為所有等待時間的總和= 0 1 4 6 = 11，這是我們可以從任何執行順序中獲得的最低分數。
我們的任務是找到這個最低分數。
我們如何解決這個問題？我嘗試嘗試每次選擇最少三個元素的方法，但這是不正確的，因為當遇到兩個或三個相同的元素時它會卡住。
再舉一個例子：
如果A1=[23,10,18,43], A2=[7], A3=[13,42]最低分數是 307。
uj5u.com熱心網友回復：
解決這個問題的最簡單方法是使用動態規劃（以立方時間運行）。
對于每個 array A：假設您從 array 中獲取第一個元素A， ie A[0]，作為下一個程序。您的總成本是A[0]（即A[0] * (total_remaining_elements - 1)）的等待時間貢獻，加上來自A[1:]和其余陣列的最小等待時間總和。
對每個可能的第一個陣列取最低成本A，您將獲得最低分數。
這是該想法的 Python 實作。它適用于任意數量的陣列，而不僅僅是三個。
def dp_solve(arrays: List[List[int]]) -> int:
"""Given list of arrays representing dependent processing times,
return the smallest sum of wait_time_before_start for all job orders"""
arrays = [x for x in arrays if len(x) > 0] # Remove empty
@functools.lru_cache(100000)
def dp(remaining_elements: Tuple[int],
total_remaining: int) -> int:
"""Returns minimum wait time sum when suffixes of each array
have lengths in 'remaining_elements' """
if total_remaining == 0:
return 0
rem_elements_copy = list(remaining_elements)
best = 10 ** 20
for i, x in enumerate(remaining_elements):
if x == 0:
continue
cost_here = arrays[i][-x] * (total_remaining - 1)
if cost_here >= best:
continue
rem_elements_copy[i] -= 1
best = min(best,
dp(tuple(rem_elements_copy), total_remaining - 1)
cost_here)
rem_elements_copy[i] = 1
return best
return dp(tuple(map(len, arrays)), sum(map(len, arrays)))
更好的解決方案
“最小的第一個元素”的幼稚貪婪策略不起作用，因為做更長的作業以在同一個串列中完成更短的作業是值得的，例如
A1 = [100, 1, 2, 3], A2 = [38], A3 = [34],
best solution = [100, 1, 2, 3, 34, 38]
由user3386109在評論中演示。
A more refined greedy strategy does work. Instead of the smallest first element, consider each possible prefix of the array. We want to pick the array with the smallest prefix, where prefixes are compared by average process time, and perform all the processes in that prefix in order.
A1 = [ 100, 1, 2, 3]
Prefix averages = [(100)/1, (100 1)/2, (100 1 2)/3, (100 1 2 3)/4]
= [ 100.0, 50.5, 34.333, 26.5]
A2=[38]
A3=[34]
Smallest prefix average in any array is 26.5, so pick
the prefix [100, 1, 2, 3] to complete first.
Then [34] is the next prefix, and [38] is the final prefix.
And here's a rough Python implementation of the greedy algorithm. This code computes subarray averages in a completely naive/brute-force way, so the algorithm is still quadratic (but an improvement over the dynamic programming method). Also, it computes 'maximum suffixes' instead of 'minimum prefixes' for ease of coding, but the two strategies are equivalent.
def greedy_solve(arrays: List[List[int]]) -> int:
"""Given list of arrays representing dependent processing times,
return the smallest sum of wait_time_before_start for all job orders"""
def max_suffix_avg(arr: List[int]):
"""Given arr, return value and length of max-average suffix"""
if len(arr) == 0:
return (-math.inf, 0)
best_len = 1
best = -math.inf
curr_sum = 0.0
for i, x in enumerate(reversed(arr), 1):
curr_sum = x
new_avg = curr_sum / i
if new_avg >= best:
best = new_avg
best_len = i
return (best, best_len)
arrays = [x for x in arrays if len(x) > 0] # Remove empty
total_time_sum = sum(sum(x) for x in arrays)
my_averages = [max_suffix_avg(arr) for arr in arrays]
total_cost = 0
while True:
largest_avg_idx = max(range(len(arrays)),
key=lambda y: my_averages[y][0])
_, n_to_remove = my_averages[largest_avg_idx]
if n_to_remove == 0:
break
for _ in range(n_to_remove):
total_time_sum -= arrays[largest_avg_idx].pop()
total_cost = total_time_sum
# Recompute the changed array's avg
my_averages[largest_avg_idx] = max_suffix_avg(arrays[largest_avg_idx])
return total_cost
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/434660.html