Hardprob/Maximum Integer K-Choice Knapsack — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Неотрицательные целочисленные <em>m×k</em> матрицы <m>A,…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Неотрицательные целочисленные <em>m×k</em> матрицы <m>A, C | + | * Неотрицательные целочисленные <em>m×k</em> матрицы <m>A, C ∈ N^{m\cdot k}</m>, неотрицательное целое <em>b∈ N</em>. |
* Найти | * Найти | ||
| − | ** неотрицательный целочисленный <em>n</em>-вектор <m> | + | ** неотрицательный целочисленный <em>n</em>-вектор <m>x∈ N^n</m>, |
** функция <m>f: [1..n] → [1..k]</m> | ** функция <m>f: [1..n] → [1..k]</m> | ||
** такие, что <m>\displaystyle\sum\limits_{i=1}^{n} a_{i,f(i)} x_i\le b</m>. | ** такие, что <m>\displaystyle\sum\limits_{i=1}^{n} a_{i,f(i)} x_i\le b</m>. | ||
Версия 18:00, 17 апреля 2023
- Неотрицательные целочисленные m×k матрицы , неотрицательное целое b∈ N.
- Найти
- неотрицательный целочисленный n-вектор ,
- функция
- такие, что .
- Максимизировать
.
Код в «maximum-integer-k-choice-knapsack.ipynb» на гитлаб или живьем в лабе
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «MP11» (аналог)