Взвешенное планирование заданий с использованием рекурсии

Question

Я пытался решить проблему грубой силы взвешенного планирования работы .

Это то, что я пробовал.

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]].Когда я выполняю программу, она возвращает мне 170, то есть когда порядок выполнения равен 1-> 2-> 3.Однако ожидаемый результат равен 250 при выполнении в порядке 1-> 4.

Может ли кто-нибудь указать на мою ошибку?

Answer 1

Ваш цикл for (let i = 0; i < jobs.length; i++) { работает только для i = 0, как вы позже делаете return weight + maxWeight;.Не уверен, почему у вас есть эта строка, я думаю, вы должны сделать

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