找到可能的最低分数

Question

问题陈述:

我们得到三个长度为 n1,n2,n3 的数组 A1,A2,A3。每个数组包含一些（或没有）自然数（即 > 0）。这些数字表示程序执行时间。
任务是从任何数组中选择第一个元素，然后您可以执行该程序并将其从该数组中删除。

例如：

if A1=[3,2] (n1=2),  
   A2=[7] (n2=1),  
   A3=[1] (n3=1)

然后我们可以按[1,7,3,2]或[7,1,3,2]或[3,7,1,2]或[3,1,7,2]或[3,2,1,7]等各种顺序执行程序

现在如果我们以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。

Answer 1

解决此问题的最简单方法是使用动态规划（以立方时间运行）。

对于每个数组A：假设你从数组A中取出第一个元素，即A[0]作为下一个过程。您的总成本是 A[0]（即 A[0] * (total_remaining_elements - 1)）的 wait-time 贡献，加上 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)))

更好的解决方案

'smallest first element' 的幼稚贪婪策略不起作用，因为在同一个列表中完成更短的工作可能值得做更长的工作，例如

A1 = [100, 1, 2, 3], A2 = [38], A3 = [34],
best solution = [100, 1, 2, 3, 34, 38]

由user3386109在评论中演示。

更精细的贪婪策略确实有效。 考虑数组的每个可能前缀而不是最小的第一个元素。我们想选择前缀最小的数组，其中前缀与平均处理时间进行比较，并按顺序执行该前缀中的所有处理。

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.

这里是贪心算法的粗略 Python 实现。此代码以完全 naive/brute-force 的方式计算子数组平均值，因此该算法仍然是二次算法（但比动态规划方法有所改进）。此外，为了便于编码，它计算 'maximum suffixes' 而不是 'minimum prefixes'，但这两种策略是等价的。

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

找到可能的最低分数

Find Minimum Score Possible

arrays

algorithm

data-structures