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

Текущая версия на 22:05, 17 апреля 2023

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

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Нужно хранить некий набор <em>A</em> каких-то штук, каждая <m>a∈  A</m> из которых имеет
+* Нужно хранить некий набор <em>A</em> каких-то штук, каждая <em>a ∈ A</em> из которых имеет
 ** размер <m>s(a)∈  Z^+</m>
 ** время прибытия <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>σ: A →  Z^{+}</m>, такая что для любых <em>a,a'∈ A</em>, если <m>I(a) ∩  I(a')</m> непусто, то либо <m>d(a) ≤ r(a')</m>, либо <m>d(a') ≤ r(a)</m>.
 * Минимизировать максимальный требуемый размер, т.е.
-  <m>\max_{a ∈  A}(\sigma(a)+s(a)-1) → \min</m>.
+  <m>\max_{a ∈  A}(σ(a)+s(a)-1) → \min</m>.
 ----