Блог

Главная - Вопросы по программированию - Алгоритм планирования задач

Алгоритм планирования задач

#algorithm #scheduled-tasks #dynamic-programming

#алгоритм #запланированные задачи #динамическое программирование

Вопрос:

Как мне решить следующую проблему? У меня есть смысл использовать DP

Учитывая массив сложности задачи, обратите внимание, что сложность также зависит от порядка выполнения задачи, которую они должны выполнить. Ограничение состоит в том, чтобы каждый день планировалось хотя бы одно задание. Сложность этого дня является самой высокой сложностью задачи за этот день. Какова общая минимальная сложность, которая может быть достигнута при оптимальном планировании?

Например, допустим, есть n = 5 задачи, в которых:

 complexity = [1, 5, 3, 2, 4]

и длина теста равна days = 2 . Лучший вариант — выполнить первую задачу в первый день, а остальные — на второй день. Сложность первого дня будет равна 1, поскольку это единственная задача, а сложность второго дня будет равна 5, поскольку это уровень сложности самой сложной задачи в этот день. Следовательно, ответ таков 1 5 = 6 .

 Example 1:
5 -> complexity[] size n = 5
30
10
40
20
50
2 -> Days =2

Вывод:

 80

Комментарии:

1. Я не мог понять, какой выбор 1 5 = 6 является оптимальным в вашем примере, Note that the complexity is also the order of the task they need to be executed , не могли бы вы уточнить, в каком порядке?, если вы имеете в виду массив по порядку, то, я думаю, формулировка проблемы была бы неправильной.

2. @4.Pi.n не порядок индексов. Это означает, что мне нужно сначала выполнить задачу со сложностью 1, затем задачу со сложностью 2, затем 3… в первом примере.

3. В вашем примере, почему вы выбираете 1 5 = 6 , чтобы быть оптимальным, почему бы не выбрать 1 2 = 3 , какое ограничение подразумевает этот выбор ?.

4. из-за этого описания: «сложность этого дня является самой высокой сложностью задачи этого дня». итак, в первый день мы завершаем 1, во второй день мы завершаем 2,3,4,5, так что общая сложность равна 1 5 = 6

5. извините, я думаю, вы правы насчет порядка. Я думаю, это действительно означает, что задача должна быть спланирована в соответствии с индексами. В противном случае ответ на пример 1 должен быть 60 вместо 80.@4.Pi.n

Ответ №1:

Я думаю, что это O (n 2), поэтому не очень оптимально, но это работает. Он написан на Go.

 package main

import "fmt"

func optimize(tasks []int, days int) int {
    // edge case 1: empty c or days <= 0
    // (this is really for data input validation)
    if len(tasks) == 0 || days <= 0 {
        return 0
    }
    // edge case 2: single day - return max
    if days == 1 {
        max := tasks[0]
        for _, v := range tasks[1:] {
            if v > max {
                max = v
            }
        }
        return max
    }
    // edge case 3: tasks = days
    if days == len(tasks) {
        total := 0
        for _, v := range tasks {
            total  = v
        }
        return total
    }
    // all other cases:
    possibilities := []int{}
    i := 0
    max := tasks[0]
    for {
        tasksLeft := len(tasks[i 1:])
        daysLeft := days - 1
        if tasksLeft < daysLeft {
            break
        }
        if tasks[i] > max {
            max = tasks[i]
        }
        possibility := max   optimize(tasks[i 1:], days-1)
        possibilities = append(possibilities, possibility)
        i  
    }
    // minimize
    min := possibilities[0]
    for _, p := range possibilities[1:] {
        if p < min {
            min = p
        }
    }
    return min
}

func main() {
    tasks := []int{1, 5, 3, 2, 4}
    days := 2
    fmt.Println(optimize(tasks, days))
}