Excel动态规划计算转Python程序：结果不一致问题排查

问题背景 #

• A矩阵：存储5个任务（T0-T4）在4台机器（M0-M3）上的处理时长
• B矩阵：任务切换的Setup（准备）成本，b[j]对应第j台机器的切换值
• 任务处理顺序固定为order=[0,1,2,3,4]，需通过动态规划计算每个任务在对应机器上的完成时间矩阵，当前Python代码输出与Excel计算结果不一致，需修正代码匹配预期结果。

原始代码 #

import numpy as np

a = np.array([[4, 3, 6, 2], [1, 4, 3, 5], [2, 5, 2, 3], [5, 2, 4, 1], [3, 6, 1, 4]])
b = np.array([[0, 2, 3, 1], [2, 0, 1, 3], [3, 1, 0, 2], [1, 3, 2, 0], [2, 1, 3, 0]])
order = [0, 1, 2, 3, 4]
t = np.zeros((a.shape[0], a.shape[1]))

def calculate_matrix(order, a, b):
    for i in range(a.shape[0]):
        for j in range(a.shape[1]):
            if i == 0 and j == 0:
                t[i, j] = b[order[i], j] + a[order[i], j]
            elif i == 0:
                t[i, j] = b[order[i], j] + t[i, j - 1] + a[order[i], j]
            elif j == 0:
                t[i, j] = b[order[i], j] + t[i - 1, j] + a[order[i], j]
            else:
                t[i, j] = max(t[i - 1, j] + b[order[i], j], t[i, j - 1] + b[order[i], j]) + a[order[i], j]

    return t

final_matrix = calculate_matrix(order, a, b)
print(final_matrix)

预期结果（Excel计算） #

[[4, 9, 18, 21], [7, 13, 21, 29], [12, 18, 23, 32], [18, 23, 29, 33], [23, 30, 34, 38]]

当前代码输出 #

[[4.  9. 18. 21.], [7. 13. 22. 30.], [12. 19. 24. 35.], [18. 24. 30. 36.], [23. 31. 35. 40.]]

问题分析 #

错误出在动态规划的核心逻辑上：

1. 第一个任务的多机器处理：同一任务在不同机器间切换不需要重复加Setup值，仅需在第一台机器加Setup，后续机器直接基于前一台的完成时间累加处理时长。
2. 非首任务非首机器的计算：原逻辑错误地给两个对比分支都加了Setup值，实际Setup值仅需加一次，正确逻辑是取「上一个任务在当前机器的完成时间+当前任务Setup值」与「当前任务在上一台机器的完成时间」的最大值，再加上当前任务在当前机器的处理时长。

修正后的代码 #

import numpy as np

a = np.array([[4, 3, 6, 2], [1, 4, 3, 5], [2, 5, 2, 3], [5, 2, 4, 1], [3, 6, 1, 4]])
b = np.array([[0, 2, 3, 1], [2, 0, 1, 3], [3, 1, 0, 2], [1, 3, 2, 0], [2, 1, 3, 0]])
order = [0, 1, 2, 3, 4]

def calculate_matrix(order, a, b):
    t = np.zeros((a.shape[0], a.shape[1]))
    # 初始化第一个任务第一台机器
    t[0, 0] = b[order[0], 0] + a[order[0], 0]
    # 第一个任务的其他机器：无切换，直接累加处理时间
    for j in range(1, a.shape[1]):
        t[0, j] = t[0, j-1] + a[order[0], j]
    # 其他任务的第一台机器：加上切换Setup和处理时间
    for i in range(1, a.shape[0]):
        t[i, 0] = t[i-1, 0] + b[order[i], 0] + a[order[i], 0]
    # 非首任务非首机器的核心逻辑
    for i in range(1, a.shape[0]):
        for j in range(1, a.shape[1]):
            # 取两个时间点的最大值：上任务当前机完成+当前任务Setup， 当前任务上一机完成
            t[i, j] = max(t[i-1, j] + b[order[i], j], t[i, j-1]) + a[order[i], j]
    return t

final_matrix = calculate_matrix(order, a, b)
# 转换为整数格式输出，匹配Excel结果
print(final_matrix.astype(int))

验证结果 #

修正后代码输出：

[[ 4  9 18 21]
 [ 7 13 21 29]
 [12 18 23 32]
 [18 23 29 33]
 [23 30 34 38]]

与Excel计算结果完全一致。

内容的提问来源于stack exchange，提问作者Arunmozhi