最优加工次序问题的python实现

最优加工次序问题是一个经典的动态规划问题，可以使用Python来实现。以下是一个简单的代码示例：

def optimal_order(n, times):
    """
    n: 任务数量
    times: 执行每个任务所需的时间，是一个长度为n的列表
    """
    # 初始化dp数组，dp[i][j]表示前i个任务在j台机器上的最短完成时间
    dp = [[0] * (n+1) for _ in range(n+1)]
    # 初始化边界条件
    for i in range(1, n+1):
        dp[i][1] = dp[i-1][1] + times[i-1]
    for j in range(1, n+1):
        dp[1][j] = times[0]
    # 动态转移
    for i in range(2, n+1):
        for j in range(2, n+1):
            min_time = float('inf')
            for k in range(1, i):
                time = max(dp[k][j-1], sum(times[k:i]))
                if time < min_time:
                    min_time = time
            dp[i][j] = min_time
    # 返回结果
    return dp[n][n]

上述代码使用了二维数组来保存状态，时间复杂度为O(n^3)，可以通过一些优化来降低时间复杂度，例如使用滚动数组来节省空间，使用二分查找来加速查找过程等等。