使用递归的加权作业调度

Question

我正在尝试用蛮力解决 weighted job scheduling 问题。

这是我试过的。

const solution = jobs => {
  let maxWeight = 0;

  for (let i = 0; i < jobs.length; i++) {
    const endTime = jobs[i][1];
    const weight = jobs[i][2];

    const filteredJobs = jobs.filter(
      (job, index) => job[0] >= endTime);

    const returnedWeight = solution(filteredJobs);
    if (returnedWeight > maxWeight) {
      maxWeight = returnedWeight;
    }
    return weight + maxWeight;
  }
  return maxWeight;
};

我用来测试我的解决方案的输入是 [[1, 2, 50], [3, 5, 20], [6, 19, 100], [2, 100, 200]]。当我执行程序时，它 returns me 170 即当执行顺序为 1->2->3 时。然而，当按 1->4.

顺序执行时，预期输出为 250

谁能指出我的错误？

Answer 1

您的循环 for (let i = 0; i < jobs.length; i++) { 仅在 i = 0 时运行，您稍后会执行 return weight + maxWeight;。不确定你为什么有那条线，我猜你是故意的

  if (returnedWeight + weight > maxWeight) {
    maxWeight = returnedWeight + weight;
  }

使用递归的加权作业调度

Weighted Job Scheduling using Recursion

javascript

algorithm

recursion

job-scheduling

recursive-backtracking