Планирование сборочной линии - структуры данных

Question

Я изо всех сил пытаюсь понять, как вычисляется таблица в этой задаче «Планирование сборочных линий» в главе 15 «Динамическое программирование» книги Кормена «Введение в алгоритмы».

Может кто-нибудь подсказать мнео чем две таблицы и как они рассчитываются?Поиск в Google в течение последних 2 часов.

Answer 1

f(2) = 22 потому что это самый короткий путь (время) для прохождения станции 2,3 :)
Вы должны посмотреть все пути и найти самую короткую f(1)j станцию ​​1,j
Я знаю потому что я тоже взял этот урок:)

Answer 2

1-я таблица содержит самый быстрый способ пройти станцию ​​Si, j:

• f1 [j] - самый быстрый способ пройти станцию ​​j конвейера 1
• f2 [j] - самый быстрый способ пройти станцию ​​j сборочной линии 2

Например, f2 (3) = 22 * ​​1010 *, так как 2 + 7 + 2 + 5 + 6 = 22 * ​​1012 *, и это самый быстрый способ пройти станцию ​​3 сборки строка 2.

Во 2-й таблице li (j) показывает номер сборочной линии (1 или 2), который используется на шаге j-1 как часть самого быстрого способа достижения li (j).

Например, l1 (2) = 1 , поскольку самый быстрый способ добраться до станции 2 на сборочной линии 1 - через станцию ​​1 на сборочной линии 1 . (2 + 7 <4 + 8 + 2) </p>

l2 (2) = 1 , поскольку самый быстрый способ добраться до станции 2 на сборочной линии 2 - через станцию ​​1 на сборочной линии 1 . (2 + 7 + 2 <4 + 8). </p>

Answer 3

Извините, что выкопал 4-летний вопрос, но это первый результат в Google.

Ответ, предоставленный Лиором, неверен. f1 (j) НЕ для проходящих станций, начинающихся на конвейере 1. Если это так, почему f1 (2) = 18? когда оптимальный путь 2 + 7 + 2 + 5 = 16.

Кроме того, для f2 (3) = 22, 4 + 8 + 5 + 1 + 3 НЕ равно 22. Это 21.

fi (j) на самом деле является функцией самого быстрого способа добраться до j-й станции на i-й линии (как ответил Кубра). f2 (3) = 22, потому что 2 + 7 + 2 + 5 + 6. Это самый эффективный маршрут, чтобы добраться до этой конкретной станции.

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

Спасибо.