Это мой первый эксперимент с проблемой асимптотической сложности, хотя я доволен ответами полностью в коде, если они приходят с объяснением сложности времени.

У меня следующая проблема.

Рассмотрим задачи T_1, ... T_n и процы M_1, ..., M_m. Каждая задача занимает определенное количество времени для выполнения в зависимости от процедур.

Каждое задание также стоит определенной суммы для выполнения в зависимости от процедур.

Задачи должны выполняться в строгом порядке (их нельзя выполнять параллельно), и для изменения процедуры требуется время. Задание не может быть перемещено из одного процесса в другой после его запуска.

Наконец, каждое задание должно быть выполнено к определенному времени.

задание

Задача состоит в том, чтобы дать алгоритм (или некоторый код), который с учетом пяти таблиц в приведенной выше форме минимизирует общую стоимость выполнения всех задач, при этом гарантируя, что все задачи будут выполнены в установленные сроки. Если это невозможно, мы просто сообщаем, что это невозможно сделать.

Гол

Вы должны дать большую сложность своего решения в терминах переменных n, m и d, где d - последний срок. В вашей большой сложности не должно быть лишних констант. Таким образом, O (n / 1000) должно быть записано как O (n), например.

Ваша оценка рассчитывается просто путем установки n = 100, m = 100 и d = 1000 в вашей заявленной сложности. Вы хотите наименьшее возможное количество баллов.

прерыватель связи

В случае ничьей победит первый ответ.

добавленные заметки

log во время сложности ответа будет принята основа 2.

табло

• 10 ^ 202 от KSFT ( Python ) Сначала отправлено, поэтому получает награду.
• 10 ^ 202 от Доминика Мюллера ( Скала )

Оценка: 10 ^ 202

Я бы хотел, чтобы у нас была поддержка LaTeX сейчас ...

Поскольку никто не ответил, я подумал, что попробую, хотя это не очень эффективно. Хотя я не уверен, что это за большой смысл.

Я думаю, что это работает. По крайней мере, это относится к единственному тестовому сообщению.

Он принимает ввод, как в вопросе, за исключением того, что без меток номера машины или задачи и с точками с запятой вместо разрывов строк.

import itertools
time = [[int(j) for j in i.split()] for i in raw_input().split(";")]
cost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
nmachines=len(time)
ntasks=len(time[0])
switchtime = [[int(j) for j in i.split()] for i in raw_input().split(";")]
switchcost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
deadline = [int(i) for i in raw_input().split()]
d={}
m=itertools.product(range(nmachines),repeat=ntasks)
for i in m:
    t=-switchtime[i[-1]][i[0]]
    c=-switchcost[i[-1]][i[0]]
    e=0
    meetsdeadline=True
    for j in range(ntasks):
        t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
        c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
        e+=1
        if t>deadline[j]:
            meetsdeadline=False
    if meetsdeadline:
        d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]

Проверить все - Scala

Ориентировочный балл: 2m ^ n

Я начинаю с каждой машины и перебираю все задачи для создания всех перестановок в задачах с разными машинами, которые соответствуют срокам. То есть, если бы все было вовремя, я бы получил 9 возможных путей с 2 ​​машинами и 3 задачами. (m ^ n) После этого я выбираю путь с наименьшими затратами.

Ввод структурирован следующим образом (-> объясняет части и поэтому не должен вводиться):

M_1:5 3 5 4;M_2:4 2 7 5                 --> time
M_1:5 4 2 6;M_2:3 7 3 3                 --> cost
M_1:M_1}0 M_2}1;M_2:M_1}2 M_2}0         --> switch itme
M_1:M_1}0 M_2}2;M_2:M_1}1 M_2}0         --> switch cost
5 10 15 20                              --> deadlines

И вот код:

package Scheduling

import scala.io.StdIn.readLine

case class Cost(task: Map[String, List[Int]])
case class Switch(machine: Map[String, Map[String, Int]])
case class Path(time: Int, cost: Int, machine: List[String])

object Main {

    def main(args: Array[String]) {
        val (machines, cost_time, cost_money, switch_time, switch_money, deadlines) = getInput

        val s = new Scheduler(machines, cost_time, cost_money, switch_time, switch_money, deadlines)
        s.schedule
    }

    def getInput(): (List[String], Cost, Cost, Switch, Switch, List[Int]) = {
        val cost_time = Cost(readLine("time to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val cost_money = Cost(readLine("cost to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val switch_time = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val switch_money = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val deadlines = readLine("deadlines").split(" ").map(_.toInt).toList

        val machines = cost_time.task.keys.toList

        (machines, cost_time, cost_money, switch_time, switch_money, deadlines)
    }
}

class Scheduler(machines: List[String], cost_time: Cost, cost_money: Cost, switch_time: Switch, switch_money: Switch, deadlines: List[Int]) {

    def schedule() {
        var paths = List[Path]()
        var alternatives = List[(Int, Path)]()

        for (i <- machines) {
            if (cost_time.task(i)(0) <= deadlines(0)) {
                paths = paths ::: List(Path(cost_time.task(i)(0), cost_money.task(i)(0), List(i)))
            }
        }

        val allPaths = deadlines.zipWithIndex.tail.foldLeft(paths)((paths, b) => paths.flatMap(x => calculatePath(x, b._1, b._2)))

        if (allPaths.isEmpty) {
            println("It is not possible")
        } else {
            println(allPaths.minBy(p=>p.cost).machine)
        }
    }

    def calculatePath(prev: Path, deadline: Int, task: Int): List[Path] = {
        val paths = machines.map(m => calculatePath(prev, task, m))
        paths.filter(p => p.time <= deadline)
    }

    def calculatePath(prev: Path, task: Int, machine: String): Path = {
        val time = prev.time + switch_time.machine(prev.machine.last)(machine) + cost_time.task(machine)(task)
        val cost = prev.cost + switch_money.machine(prev.machine.last)(machine) + cost_money.task(machine)(task)

        Path(time, cost, prev.machine :+ machine)
    }
}

У меня также была идея начать со спины. Так как вы всегда можете выбрать машину с наименьшей стоимостью, если время меньше, то разница от предыдущего срока до нового. Но это не уменьшит максимальное время выполнения, если задача с лучшими затратами займет больше времени, чем установлен последний срок.

Обновить

======

Вот еще одна установка. время:

M_1 2 2 2 7
M_2 1 8 5 10

Стоимость:

M_1 4 4 4 4
M_2 1 1 1 1

время переключения:

    M_1 M_2
M_1  0   2
M_2  6   0

Стоимость переключения:

    M_1 M_2
M_1  0   2
M_2  2   0

сроки:

5 10 15 20

Как вход в мою программу:

M_1:2 2 2 7;M_2:1 8 5 10
M_1:4 4 4 4;M_2:1 1 1 1
M_1:M_1}0 M_2}2;M_2:M_1}6 M_2}0
M_1:M_1}0 M_2}2;M_2:M_1}2 M_2}0
5 10 15 20

У этого есть два решения: время: 18, стоимость: 15, путь: список (M_1, M_1, M_1, M_2) время: 18, стоимость: 15, путь: список (M_2, M_1, M_1, M_1)

Что поднимает вопрос, как это должно быть обработано. Должны ли все быть напечатаны или только один? А что если время будет другим? Является ли тот, который имеет наименьшую стоимость и не пропущен крайний срок, достаточно ли, или он также должен быть с наименьшим временем?