动态规划将任务分配给不同的计算机

Question

我有以下动态规划问题，我无法弄明白。

基本上你有一个像这样的 table 代表计算机 X 完成 Y 任务所花费的时间（ordi 表示计算机）。

在这种情况下，计算机 1 将花费 7 秒来完成 1 个任务，10 秒来完成 2 个任务，依此类推

计算机 2 完成 1 个任务需要 8 秒，完成 2 个任务需要 9 秒，依此类推

现在，我想编写一个动态规划算法，告诉我计算机 1 和 2 完成 3 个任务所需的最少时间，或者计算机 1、2 和 3 完成 5 个任务所需的最少时间任务等

记住 2 个约束： 每台涉及的计算机必须至少分配 1 个任务，并且所有 6 个任务必须分发。例如，您不能使用计算机 1 和 2 完成 1 项任务，就像您不能使用 3 台计算机完成少于 3 项任务一样（并且每台计算机都必须有一项任务）。

这是解决方案：

我的（几乎可以工作的）(Rust) 代码在下面，它没有给出正确的数字，但是，任何人都可以得到它来给出正确的解决方案吗？

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],
];

let mut optimal = vec![vec![999999999; costs[0].len()]; costs.len()];

for j in 0..costs[0].len() {
    optimal[0][j] = costs[0][j];
}

for i in 1..optimal.len() {
    for j in i..optimal[i].len() {
        let mut min = 999999999;

        for k in 0..j {
            let c = optimal[i - 1][j - k] + costs[i][k];
            min = std::cmp::min(c, min);
        }
        optimal[i][j] = min;
    }
}

Answer 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],
];

let mut optimal = vec![vec![999999999; costs[0].len()]; costs.len()];

for j in 0..costs[0].len() {
    optimal[0][j] = costs[0][j];
}

for i in 1..optimal.len() {
    for j in i..optimal[i].len() {
        let mut min = 999999999;

        //Wrong interval
        for k in 1..j+1 {
            //Index shift because we start with 0
            let c = optimal[i - 1][j - k] + costs[i][k-1];
            min = std::cmp::min(c, min);
        }
        optimal[i][j] = min;
    }
}

您基本上没有考虑到 1 个任务的列在第 0 列中，依此类推，因此您将得到 2 个索引偏移。

动态规划将任务分配给不同的计算机

Dynamic programming assigning tasks to different computers

algorithm

dynamic-programming

rust