Hardprob/Minimum Dynamic Storage Allocation — различия между версиями

Версия 21:47, 17 апреля 2023

Нужно хранить некий набор A каких-то штук, каждая из которых имеет
- размер
- время прибытия
- время отбытия
Найти допустимый план резервирования места хранения, т.е. функция , такая что для любых a,a'∈ A, если непусто, то либо , либо .
Минимизировать максимальный требуемый размер, т.е.

@@ Строка 4: / Строка 4: @@
 ** время прибытия <m>r(a) ∈  Z^{+}</m>
 ** время отбытия <m>d(a) ∈  Z^{+}</m>
-* Найти допустимый план резервирования места хранения, т.е. функция <m>\sigma: A →  Z^{+}</m>, такая что для любых <m>a,a' ∈  A</m>, если <m>I(a) \cap I(a')</m> непусто, то либо <m>d(a) ≤ r(a')</m>, либо <m>d(a') ≤ r(a)</m>.
+* Найти допустимый план резервирования места хранения, т.е. функция <m>\sigma: A →  Z^{+}</m>, такая что для любых <em>a,a'∈ A</em>, если <m>I(a) \cap I(a')</m> непусто, то либо <m>d(a) ≤ r(a')</m>, либо <m>d(a') ≤ r(a)</m>.
 * Минимизировать максимальный требуемый размер, т.е.