Hardprob/Maximum Class-Constrained Knapsack - История изменений

StasFomin в 07:58, 30 апреля 2023

2023-04-30T07:58:53Z

StasFomin в 21:15, 26 апреля 2023

2023-04-26T21:15:57Z

StasFomin: Массовая правка: замена PCRE \\le\s на ≤

2023-04-17T21:28:00Z

Массовая правка: замена PCRE \\le\s на ≤

StasFomin: Массовая правка: замена \in на ∈

2023-04-17T18:00:13Z

Массовая правка: замена \in на ∈

StasFomin: Массовая правка: замена \times на ×

2023-04-17T11:36:52Z

Массовая правка: замена \times на ×

StasFomin: Новая страница: « * n размеров заданных вектором U \in N^n, m р…»

2023-04-13T13:46:13Z

Новая страница: « * n размеров заданных вектором <m>U \in N^n</m>, m р…»

Новая страница

* n размеров заданных вектором <m>U \in N^n</m>, m рюкзаков разных размеров и числом отсеков заданных векторами <m>V \in N^m, C \in N ^m</m>, причем <m>\sum_i U_i = \sum_j V_j</m>.
* Найти размещение заданных элементов в эти рюкзаки, заданный двумя n×m матрицами,
<m>I \in \{0,1\}^{n\times m}, Q \in N ^{n\times m}</m>, такой, что
** <m>\sum_i Q_{i,j} \le V_j \ \ ∀j</m>
** <m>\sum_i I_{i,j} \le C_j \ \ ∀j</m>
** <m>\sum_j Q_{i,j} \le U_i \ \ ∀i</m>
** <m>I_{i,j}=0 \Rightarrow Q_{i,j}=0 \ \ ∀i,j </m>
* Максимизировать число упакованных элементов
<m>\sum_i \sum_j Q_{i,j} → \max</m>.

----
{{hard-problem-on-lab17|{{PAGENAME}}}}




----

{{ViggoCode|node214}}





[[Категория:ClassicHardProblems]]

@@ Строка 3: / Строка 3: @@
 * Найти размещение заданных элементов в эти рюкзаки, заданный двумя <em>n×m</em> матрицами,
 <m>I ∈  \{0,1\}^{n× m}, Q ∈  N ^{n× m}</m>, такой, что
-** <m>\sum_i Q_{i,j} \le V_j \ \ ∀j</m>
+** <m>\sum_i Q_{i,j} ≤V_j \ \ ∀j</m>
-** <m>\sum_i I_{i,j} \le C_j \ \ ∀j</m>
+** <m>\sum_i I_{i,j} ≤C_j \ \ ∀j</m>
-** <m>\sum_j Q_{i,j} \le U_i \ \ ∀i</m>
+** <m>\sum_j Q_{i,j} ≤U_i \ \ ∀i</m>
 ** <m>I_{i,j}=0 \Rightarrow Q_{i,j}=0 \ \ ∀i,j </m>
 * Максимизировать число упакованных элементов

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* <em>n</em> размеров заданных вектором <m>U \in N^n</m>, <em>m</em> рюкзаков разных размеров и числом отсеков заданных векторами <m>V \in N^m, C \in N ^m</m>, причем <m>\sum_i U_i = \sum_j V_j</m>.
+* <em>n</em> размеров заданных вектором <m>U ∈  N^n</m>, <em>m</em> рюкзаков разных размеров и числом отсеков заданных векторами <m>V ∈  N^m, C ∈  N ^m</m>, причем <m>\sum_i U_i = \sum_j V_j</m>.
 * Найти размещение заданных элементов в эти рюкзаки, заданный двумя <em>n×m</em> матрицами,
-<m>I \in \{0,1\}^{n× m}, Q \in N ^{n× m}</m>, такой, что
+<m>I ∈  \{0,1\}^{n× m}, Q ∈  N ^{n× m}</m>, такой, что
 ** <m>\sum_i Q_{i,j} \le V_j \ \ ∀j</m>
 ** <m>\sum_i I_{i,j} \le C_j \ \ ∀j</m>

@@ Строка 2: / Строка 2: @@
 * <em>n</em> размеров заданных вектором <m>U \in N^n</m>, <em>m</em> рюкзаков разных размеров и числом отсеков заданных векторами <m>V \in N^m, C \in N ^m</m>, причем <m>\sum_i U_i = \sum_j V_j</m>.
 * Найти размещение заданных элементов в эти рюкзаки, заданный двумя <em>n×m</em> матрицами,
-<m>I \in \{0,1\}^{n\times m}, Q \in N ^{n\times m}</m>, такой, что
+<m>I \in \{0,1\}^{n× m}, Q \in N ^{n× m}</m>, такой, что
 ** <m>\sum_i Q_{i,j} \le V_j \ \ ∀j</m>
 ** <m>\sum_i I_{i,j} \le C_j \ \ ∀j</m>

@@ Строка 24: / Строка 24: @@
 </small>
 <!-- end -->
 [[Категория:ClassicHardProblems]]