58
правок
Изменения
→Другие задачи семейства
* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>;.
===Варианты решения===
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
=== Реализация ===
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>;.
===Варианты решения===
<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;
Сложность алгоритма <tex>O(NW)</tex>.
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>;.
===Варианты решения===
W -= w[i];
else
break;
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>;.
===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако, специализированые алгоритмы, обычно более оптимальны по параметрам. Используется:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>;.
===Варианты решения===
Самые распространенные методы точного решения это:
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W </tex>;.
Сложность алгоритма <tex>O(NW)</tex>.
так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.
<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.
при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</tex>.
<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>;.
<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>;.
===Варианты решения===
