动态规划实现多计算机任务分配最小耗时求解及Rust代码修正

原代码存在的核心问题 #

• 索引错位：耗时表costs的存储顺序为「第0位对应完成1个任务的耗时、第1位对应完成2个任务的耗时……」，原代码直接以任务数为索引取值，导致所有耗时计算偏移一位，结果完全错误。
• 状态非法：原代码未落实“每台参与计算机必须至少分配1个任务”的约束，循环中允许当前计算机分配0个任务的非法情况，不符合规则要求。
• 范围校验缺失：递推时未对前序计算机的可分配任务数做合法性判断，可能出现前序计算机拿到的任务数少于自身数量、无法满足每台至少1个任务的情况；同时原数组的任务数维度长度不足，无法覆盖最大任务数的计算。

修正后可运行代码 #

let costs = [
    [7, 10, 14, 20, 21, 30],
    [8, 9, 15, 10, 18, 20],
    [9, 9, 16, 28, 30, 40],
    [11, 15, 20, 30, 35, 20],
];

// 定义状态：optimal[i][j] 表示前i+1台计算机分配j个任务，且每台至少分1个任务时的最小总耗时
const INF: i32 = 999999999;
// 列维度长度为最大任务数+1，让任务数与数组索引一一对应
let mut optimal = vec![vec![INF; costs[0].len() + 1]; costs.len()];

// 初始化第一台计算机的合法状态
for j in 1..=costs[0].len() {
    optimal[0][j] = costs[0][j - 1]; // 分配j个任务的耗时，对应数组j-1的存储位置
}

// 逐台计算机递推计算最优值
for i in 1..optimal.len() {
    // 前i+1台计算机最少需要分配i+1个任务（每台1个），最多支持到最大任务数
    for j in (i + 1)..=costs[0].len() {
        let mut min = INF;
        // k为当前第i台计算机分配的任务数，需满足两个条件：
        // 1. k >=1 （至少1个任务，符合约束）
        // 2. 剩余j-k个任务分给前i台计算机时，需保证j-k >=i（前i台每台至少1个任务）
        for k in 1..=(j - i) {
            let prev_cost = optimal[i - 1][j - k];
            let curr_cost = costs[i][k - 1];
            if prev_cost != INF {
                min = std::cmp::min(prev_cost + curr_cost, min);
            }
        }
        optimal[i][j] = min;
    }
}

结果匹配验证 #

• 2台计算机共同完成3个任务的最小耗时：取optimal[1][3]，计算结果为16秒，与参考解一致（分配方案：第1台分1个任务耗时7秒，第2台分2个任务耗时9秒，总耗时16秒）。
• 3台计算机共同完成5个任务的最小耗时：取optimal[2][5]，计算结果为25秒，与参考解一致。
• 所有计算状态均满足两项硬性约束：参与分配的计算机每台至少分到1个任务，全部任务无剩余分配完毕。

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