💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Полиномиально разрешимые подклассы труднорешаемых задач

После того, как было формализовано понятие «алгоритм», появилась возможность разделения массовых задач на разрешимые и неразрешимые. Задача неразрешима, если не существует алгоритма, ее решающего. Если та либо иная важная массовая задача неразрешима, то интерес представляет вопрос выделения ее частных случаев (подклассов), для которых можно построить решающие алгоритмы. В качестве примера приведем неразрешимую теорию – арифметику натуральных чисел; важно, что в этой теории имеются разрешимые подтеории (в частности, теория сложения натуральных чисел).

Дискретные задачи являются задачами переборного типа, каждая из них разрешима перебором конечного числа вариантов. Для таких задач в определенном смысле аналогом концепции неразрешимости является труднорешаемость (NP -полнота или NP -трудность). Естественно возникают вопросы выделения для труднорешаемых массовых задач полиномиально разрешимых подклассов; эти вопросы важны как в теоретическом плане, так и в чисто прикладном аспекте.

Рассмотрим изучавшуюся в главе 2 каноническую задачу однопроцессорного обслуживания потока заявок. Известно, что эта задача NP -трудна в сильном смысле. Результат о труднорешаемости сохраняется, если рассматривать только задачи, удовлетворяющие легко интерпретируемому и реально выполняемому в приложениях условию

t (n) ≤ с*n, (1)

где с* – фиксированная натуральная константа. Класс задач однопроцессорного обслуживания, для которых условие (1) выполняется, обозначим К [ с *]. Ниже будут рассматриваться только задачи класса К [ с *].

Через W (ρ) будет обозначаться величина суммарного штрафа по всем заявкам при условии, что их обслуживание выполняется по расписанию ρ.

Каждое из вводимых далее дополнительных ограничений на класс рассматриваемых моделей или на класс допустимых расписаний обеспечивает возможность построения для возникающих при этом оптимизационных задач полиномиальных по верхней оценке временной вычислительной сложности решающих алгоритмов. Важно, что налагаемые ограничения естественны для многих приложений.

Частная модель 1. Заявки α и β будем называть однотипными, если τ (α) = τ (β) и а (α) = а (β). Вводимое здесь ограничение касается числа типов заявок в потоке R.

Задачу класса К [ с* ] отнесем к подклассу К [ с*, m ], если во входном потоке присутствуют заявки не более чем m различных типов.

В подклассе К [ с*, m ] любое множество заявок S может быть представлено m -мерным вектором N (S) = (n ₁, n ₂,..., n_m), где n_i – число заявок i -го типа в множестве S, i = m, 1.

Вместо функции Σ (t, S) введем соответствующую функцию Σ ′ (t, N (S)), полагая для всех S

Σ (t, S) = Σ ′ (t, N (S)).

Основное рекуррентное соотношение (16) для вычисления значений функции Σ ′ в задачах подкласса К [ с*, m ] модифицируется очевидным образом, а общее количество рассматриваемых векторов (n ₁, n ₂,..., n_m), являющихся аргументами функции Σ ′, оценивается сверху величиной n^m-1. С учетом этого обстоятельства верхняя оценка числа выполняемых алгоритмом элементарных операций принимает вид С**n^m, где C** – константа, не зависящая от значений параметров m и n. Таким образом, верхняя оценка временной вычислительной сложности задач под-класса К [ с*, m ] оказывается полиномиальной.

Частная модель 2. В рамках данной модели будем считать, что количество заявок, находящихся в системе и ожидающих обслуживания, не может превысить натуральную константу k. Множество расписаний, удовлетворяющих этому ограничению, обозначим Ф(k). Рассматриваемая задача записывается в виде

(2)

Пусть Σ ^k (t, S) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, поступающим в систему обслуживания позднее момента времени t для определяемой состоянием (t, S) ситуации. При этом считается, что t – момент принятия решения, множество S заявок, ожидающих на данный момент обслуживания, не более чем (k + 1) - элементное (нулевая заявка учитывается), а допустимыми являются только расписания совокупности Ф(k).

Если в момент t начинается обслуживание заявки i, то через временной промежуток τ (i) количество r (t, i) ожидающих обслуживания заявок будет равно

| S| - sign(i) + | D (t, τ (i))|.

Обозначим через S (k, t) множество заявок i из S, для которых выполняется неравенство r (t, i) ≤ k + 1. С учетом введенных обозначений рекуррентное соотношение динамического программирования для решения задачи (2) записывается следующим образом:

(3)

Заметим, что для некоторых промежуточных состояний системы обслуживания (t, S) множество заявок S (k, t) может оказаться пустым. Такие пары считаем запрещенными, а значения соответствующих величин Σ ^k (t, S) равными ∞. Если при подсчете оказалось, что Σ ^k (0, V (0)) = ∞, то в рассматриваемой задаче множество расписаний Ф(k) пусто. С учетом принадлежности решаемой задачи классу К [ с* ], устанавливаем, что верхней оценкой временной вычислительной сложности основанного на (3) алгоритма является полином от n степени k + 1.

Частная модель 3. Будем говорить, что в расписании ρ заявка β обгоняет в обслуживании заявку α, если α < β (т.е. t (α) ≤ t (β)), но заявка β обслуживается раньше, чем заявка α. Разность β – α будем называть длиной обгона.

Расписание ρ назовем d-расписанием, если при его реализации длины обгонов не превышают натуральной константы d. Очевидно, что при реализации d -расписания произвольную за-явку i могут обогнать в обслуживании только заявки из совокупности { i + 1, i + 2,..., i + d }. Множество всех d -расписаний будем обозначать Ф[ d ].

Рассмотрим экстремальную задачу

(4)

При реализации d -расписания состояния системы – это тройки вида (t, γ, x), где t – очередной момент принятия решения по загрузке процессора (в момент t процессор считается свободным); γ – порядковый номер-наименование первой (по возрастанию номеров) необслуженной заявки; x = (х ₁, х ₂,..., х_d) – d- мерный вектор с булевозначными координатами, причем х_i = 1, если по состоянию на момент времени t заявка γ + i уже обслужена, и х_i = 0 в противном случае.

Пусть Σ ^d (t, γ, x) обозначает минимальную величину суммарного штрафа по всем необслуженным до момента времени t заявкам для системы, находящейся в состоянии (t, γ, x). При этом считается, что возможными являются только расписания из множества Ф[ d ].

Для состояния (t, γ, x) через Q (t, γ, x) обозначим совокупность всех необслуженных на данный момент t заявок. В это множество входят: заявка γ; все принадлежащие потоку R заявки γ + i такие, что х_i = 0 (здесь i = 1, 2,..., d); все принадлежащие потоку R заявки у такие, что у > γ + d. Через Q ^d (t, γ, x) обозначим подмножество заявок из Q (t, γ, x), номера-наименования которых не превосходят γ + d. Для произвольного множества заявок М через ν (М) обозначим минимальный из номеров-наименований заявок этого множества, а через w (М) обозначим вектор (w ₁, w ₂,..., w_d), в котором координата w_i = 0 тогда и только тогда, когда заявка ν (М) + i находится в множестве М; во всех остальных случаях w_i = 1; здесь i=1,..., n.

Рассмотрим общую ситуацию, когда множество Q (t, γ, x) со-стоит более чем из одной заявки. С учетом введенных обозначений, основное соотношение динамического программирования для решения задачи (4) записывается в виде

(5)

Состояние системы в последний момент принятия решения (все, кроме одной, заявки уже обслужены) записывается как тройка (t, γ *, (1, 1, …, 1)), где γ * ∈ { n – d – 1, n – d, n – d + 1, …, n }. В такой ситуации

Σ ^d (t, γ *, (1, 1, …, 1)) = a (γ *)[max (t, t (γ *)) + τ (γ *) – t (γ *)] (5')

Примем дополнительное предположение, что в рассматриваемом классе задач требуемая продолжительность обслуживания процессором любой заявки ограничена сверху некоторой константой. В таком случае в процессе вычислений по рекуррентным соотношениям (5)–(5') аргумент t функции Σ ^d (t, γ, x) принимает линейно зависящее от n число различных значений; аргумент γ принимает значения из множества {1, 2,..., n }; для возможных значений векторного аргумента x имеется не более 2 ^d вариантов. При вычислении каждого следующего значения функции число выполняемых элементарных операций линейно зависит от параметра d. Получаем, что верхней оценкой вычислительной сложности алгоритма решения задачи (4), основанного на соотношениях (5)–(5'), является

С d n ² 2 ^d,

где С – константа, не зависящая от значений параметров n и d. При любом фиксированном d верхняя оценка числа необходимых для решения задачи элементарных операций – полином второй степени от n.

Заметим, что общее число расписаний обслуживания n -элементного потока заявок в однопроцессорной системе равно n!; метод динамического программирования решает задачу синтеза оптимального расписания за экспоненциальное время. Общее число d -расписаний при любом фиксированном d зависит от n экспоненциально, но синтез оптимального d -расписания реализуется в квадратично зависящем от n времени.

Частная модель 4. Предусматривается следующее ограничение: каждую заявку могут обогнать в обслуживании не более q других заявок (q – заданная константа).

Расписание ρ назовем { q }-расписанием, если при его реализации любую заявку обгоняют в обслуживании не более q других заявок. Подкласс { q }-расписаний будем обозначать Ф{ q }.

Рассмотрим задачу синтеза оптимального { q }-расписания:

(6)

Состояния системы обслуживания – это тройки вида (t, γ, U), где t – очередной момент принятия решения по загрузке процессора (в момент t процессор считается свободным); γ – порядковый номер-наименование первой (по возрастанию номеров) не-обслуженной заявки; U – множество заявок, которые по состоянию на данный момент уже обогнали в обслуживании заявку γ, количество заявок в этом множестве не больше q (| U | ≤ q).

Пусть Σ _q (t, γ, U) обозначает минимальную величину суммарного штрафа по всем необслуженным до момента времени t за-явкам для системы, находящейся в состоянии (t, γ, U). При этом считается, что возможными являются только расписания из множества Ф{ q }.

Для состояния (t, γ, U) через Q (t, γ, U) обозначим совокупность всех необслуженных заявок; в это множество входят: за-явка γ и все заявки γ + i, не входящие в совокупность U, здесь i ∈ {1, 2, …, n – γ }. Для произвольного множества заявок М через ν (М) обозначим минимальный из номеров-наименований заявок этого множества. Через Y (М) обозначим совокупность, заявок i, i > ν (М), не входящих в множество М.

Рассмотрим общую ситуацию, когда множество Q (t, γ, U) состоит более чем из одной заявки. Если при этом | U | < q, то на немедленное обслуживание можно взять любую заявку из совокупности Q (t, γ, U); если же | U | = q, то на немедленное обслуживание в рассматриваемом состоянии следует взять заявку γ. Получаем:

(7)

для случая | U | < q;

Σ _q (t, γ, U) = a (γ) [max (t, t (γ)) + τ (γ) – t (γ)] +

+ Σ _q (t + τ (γ), ν (Q (t, γ, U) \ {γ }), Y (Q (t, γ, x) \ {γ })} (7')

для случая | U | = q.

Если множество Q (t, γ, U) состоит из единственной заявки, в таком случае это заявка γ, то

Σ _q (t, γ, U) = a (γ) [max (t, t (γ)) + τ (γ) – t (γ)]. (7'')

Примем дополнительное предположение, что в рассматриваемом классе задач продолжительность обслуживания процессором любой заявки ограничена некоторой константой. В таком случае в процессе вычислений по рекуррентным соотношениям (7)–(7 '') аргумент t функции Σ _q(t, γ, U) принимает линейно зависящее от n число различных значений; аргумент γ принимает значения из множества {1, 2,..., n }; для возможных значений аргумента U имеется не более n^q вариантов. При вычислении каждого следующего значения функции число выполняемых элементарных операций по верхней оценке линейно зависит от параметра n. Получаем, что верхней оценкой вычислительной сложности алгоритма решения задачи (6), основанного на со-отношениях (7)–(7 ''), является С n^{q +3}, где С – константа, не зависящая от значений параметров n и q.

Частная модель 5. Расписание ρ назовем (d, q) -расписанием, если при его реализации произвольная заявка i может быть обогнана в обслуживании только некоторыми заявками из совокупности { i + 1, i + 2,..., i + d } и не более чем q другими заявками. В рамках рассматриваемой модели допустимыми считаются только (d, q) - расписания. Класс (d, q) - расписаний будем обозначать Ω (d, q).

Как очевидно, класс (d, 0)-расписаний совпадает с классом d -расписаний, а класс (0, q) - расписаний совпадает с классом { q }-расписаний.

Пусть t – произвольный момент принятия решения, S – совокупность заявок, которые по состоянию на момент времени t поступили и ожидают обслуживания. Как и выше, для произвольного множества заявок М через ν (М) мы обозначаем минимальный из номеров-наименований заявок этого множества. Через η (t) обозначим максимальное значение i, для которого t (i) ≤ ≤ t, т.е. η (t) – последняя из поступивших в систему по состоянию на момент времени t заявок. Пусть

М (t, S, d) = { j |ν (S) + d < j ≤ η (t)}. (8)

Расписание ρ является (d, q) -расписанием, если при его реализации в любой момент времени t в множестве М (t, S, d) оказывается не более чем q завершенных обслуживанием заявок.

Рассмотрим задачу

(9)

При реализации (d, q)-расписания в любой момент принятия решения t совокупность Q всех оставшихся пока необслуженными заявок потока можно полностью описать (d + q + 1)-мерным вектором Х (Q) = (х ₁, х ₂,..., х_{d +1}, х ¹, х ²,..., х^q), в котором: х ₁ = ν (Q); координаты х ₂, х ₃,..., х_{d +1} – булевы, при этом х_j равно единице тогда и только тогда, когда заявка ν (Q) + j – 1 уже об-служена или заявки с данным текущим номером не существует в силу того, что ν (Q) + j – 1 > n; координаты х ¹, х ²,..., х^q перечисляют номера завершенных обслуживанием заявок из совокупности М (t, S, d). Если в совокупности М (t, S, d) обслужено только s заявок, где s < q, то х^{s +1} = х^{s +2} =... = х^q = 0. Вектор Х (Q) будем называть вектором-описанием. Доопределим Х (∅) как нуль-вектор. Если Х – вектор-описание, то пара (Х, t) – это состояние системы в момент времени t. Отметим, что по паре (Х, t) совокупность не обслуженных по состоянию на момент времени t заявок Q определяется однозначно: Q = Q (Х, t).

Пусть Ψ _dq (Х, t) обозначает минимальную величину суммарного штрафа по всем необслуженным до момента времени t заявкам для системы, находящейся в состоянии (Х, t). При этом считается, что возможными являются только расписания из множества Ω (d, q).

Начальному состоянию системы соответствует вектор-описание Х (V (0)). Поэтому

Пусть Q_dq (Х, t) – множество заявок, совпадающее с Q (Х, t), если последняя координата вектора Х нулевая, и состоящее только из заявок множества Q (Х, t) с номерами не больше ν (Q (Х, t)) + d в противном случае. При синтезе (d, q) - расписания в ситуации, определяемой парой (Х, t), выбор очередной направляемой на процессор заявки осуществляется только из совокупности Q_dq (Х, t).

Соотношение динамического программирования для решаемой задачи (9) записывается следующим образом:

(10)

При этом

Ψ _dq (Х (Æ), t (n) + θ) = 0 (11)

для любого θ > 0.

Реализация определяемой рекуррентными соотношениями (10)–(11) вычислительной процедуры осуществляется в порядке убывания значений аргумента t, процесс счета заканчивается отысканием величины Ψ _dq (Х (V (0)), 0) – оптимального значения критерия в рассматриваемой задаче (9). Отметим, что подсчет по формуле (10) каждого отдельного значения функции Ψ _dq (Х, t) выполняется в линейно зависящем от n времени. Число рассматриваемых (d + q + 1)-мерных векторов-состояний Х ограничено сверху величиной n^{q +1}2 ^d, поскольку первая и q последних координат этого вектора принимают значения из множества {1, 2,..., n }, а остальные координаты булевы. В итоге получаем, что общее число рассматриваемых наборов значений аргументов функции Ψ _dq имеет порядок n^{q +2}2 ^d, а верхней оценкой временной вычислительной сложности изложенного алгоритма решения задачи (9) оказывается О (n^{q +3}2 ^d).

Качество оптимального (d, q)-расписания зависит от выбора значений параметров: чем больше d и q, тем шире область возможных дисциплин обслуживания, что позволяет синтезировать расписания меньшей суммарной стоимости. При этом увеличение значения q на единицу предпочтительнее такого же увеличения значения d, ибо в большей степени расширяет класс допустимых расписаний. Вместе с тем, повышение значения q на единицу сопровождается ростом вычислительной сложности предложенного алгоритма в n раз, в то время как повышение на единицу значения d увеличивает число выполняемых элементарных операций лишь в два раза.

Сейчас обратимся к еще одной массовой задаче – классической задаче о ранце (КЗР); рассмотрим вопрос выделения в рамках этой общей модели полиномиально разрешимых частных классов задач.

Для решения КЗР в главе 1 был описан алгоритм А _кзр с верхней оценкой числа выполняемых элементарных операций СnW, где n – число имеющихся предметов, W – максимально допустимая величина суммарного веса помещаемых в ранец предметов, а С – константа, не зависящая от конкретных значений n и W. Внешняя простота приведенной оценки не свидетельствует о разрешимости задачи в полиномиально зависящем от объема входной информации времени. Ясно, что увеличение максимально допустимого суммарного веса помещенных в ранец предметов в 10 ^k раз влечет за собой увеличение длины записи параметра W в составе входной информации по задаче только на k десятичных разрядов. В то же время приведенная оценка числа выполняемых алгоритмом А _кзр элементарных операций возрастает в 10 ^k раз. Классическая задача о ранце относится к числу NP -трудных, ибо к ней за полиномиально зависящее от объема входной информации время сводится NP -полная задача «Разбиение» (способ построения по исходным данным задачи «Разбиение» соответствующей КЗР дан в гл. 1).

Через К _вес[ Q ] обозначим подкласс задач о ранце с n предметами, в которых вес каждого предмета не превосходит Q (n), здесь Q (n) – многочлен от одной переменной с неотрицательными коэффициентами. Так как суммарный вес всех имеющихся предметов больше W (иначе задача решается тривиальным образом – в ранец следует поместить все предметы), получаем: W < nQ (n). Для задач рассматриваемого подкласса верхней оценкой числа выполняемых алгоритмом А _кзр элементарных операций является Сn ² Q (n), т. е. полином от n. Получаем, что задачи любого подкласса К _вес[ Q ], где Q (n) – произвольная полиномиальная монотонно возрастающая функция от одной переменной, разрешимы в полиномиальном времени.

Изложим еще один, также основанный на принципе динамического программирования, способ решения КЗР. Предлагаемый алгоритм B _кзр основан на последовательном построении списков. Каждая запись любого списка имеет вид < М, С, V >, где М – подмножество предметов, С и V – соответственно суммарная стоимость и суммарный вес предметов подмножества М. Список S ⁰ считается состоящим из одной записи: < Æ, 0, 0>. Да-лее поэтапно строятся списки S ⁱ для значений i последовательно равных 1, 2, …, n. Составление каждого очередного списка S ⁱ реализуется в два шага. На первом шаге для каждой записи z = = < М, С, V > списка S ^{i − 1} определяется новая запись z* = < М È { i + 1}, С + c_{i +1}, V + v_{i +1}>, записи z и z* включаются в формируемый рабочий список Rⁱ. Результатом первого шага является список Rⁱ, содержащий в сравнении со списком S ^{i –1} вдвое больше записей. На втором шаге из списка R ⁱ изымаются: а) все за-писи, в которых значение третьей компоненты превышает W (нарушено весовое ограничение); б) каждая запись < М', С', V' >, для которой в этом же списке R ⁱ имеется запись < М'', С'', V'' > такая, что одновременно либо С' '≥ С' и V'' < V', либо С'' > С' и V'' = V'. Кроме того, если в списке R ⁱ имеются несколько записей, в которых значения вторых и третьих компонент соответственно совпадают, то все такие записи, кроме одной (любой из них), изымаются. Список S ⁱ определяется как совпадающий с получаемым в результате выполненных изъятий сокращенным списком R ⁱ. Результатом n -го этапа является список S ⁿ. В этом списке отыскиваем запись с наибольшим значением второй компоненты (суммарной стоимости). Пусть таковой является запись z ^(!)= < М ^(!), С ^(!), V ^(!)>. Получаем оптимальное решение задачи: в ранец следует поместить предметы подмножества М ^(!), максимальное значение критерия равно С ^(!).

Пример 3.1. Применением алгоритма B _кзр решить задачу:

х ₁ + 3 х ₂ + 3 х ₃ + 6 х ₄ → max;

х ₁ + х ₂ + 2 х ₃ + 4 х ₄ ≤ 6;

х_i Î {0, 1}, i = 1, 2, 3, 4.

По исходным данным сформулированной задачи строим следующие списки. Список S ⁰, как всегда, состоит из единственной записи < Æ, 0, 0>. В списке R¹ две записи: < Æ, 0, 0> и < {1}, 1, 1>. Cписок S ¹ совпадает со списком R ¹.

Список R ² включает четыре записи: < Æ, 0, 0>, < {1}, 1, 1>, < {2}, 3, 1>, < {1, 2}, 4, 2>. Список S ² получается из R ² изъятием второй записи; таким образом, S ² = {< Æ, 0, 0>, < {2}, 3, 1>, < {1, 2}, 4, 2> }.

Список R ³ включает шесть записей: < Æ, 0, 0>, < {2}, 3, 1>, < {1, 2}, 4, 2>, < {3}, 3, 2>, < {2, 3}, 6, 3>, < {1, 2, 3}, 7, 4>. Список S ³ получается из R ³ изъятием четвертой записи: S ³ = {< Æ, 0, 0>, < {2}, 3, 1>, < {1, 2}, 4, 2>, < {2, 3}, 6, 3>, < {1, 2, 3}, 7, 4> }.

Список R ⁴ включает десять записей: < Æ, 0, 0>, < {2}, 3, 1>, < {1, 2}, 4, 2>, < {2, 3}, 6, 3>, < {1, 2, 3}, 7, 4>, < {4}, 6, 4>, < {2, 4}, 9, 5>, < {1, 2, 4}, 10, 6>, < {2, 3, 4}, 12, 7>, < {1, 2, 3, 4}, 13, 8>. При составлении списка S ⁴ из R ⁴ по причине нарушения весового ограничения изымаются девятая и десятая записи; далее, в соответствии с условием изъятия б), шестая запись. В итоге получаем: S ⁴ = {< Æ, 0, 0>, < {2}, 3, 1>, < {1, 2}, 4, 2>, < {2, 3}, 6, 3>, < {1, 2, 3}, 7, 4>, < {2, 4}, 9, 5>, < {1, 2, 4}, 10, 6> }. Вторая компонента принимает наибольшее значение 10 в шестой записи последнего списка. Оптимальное решение задачи следующее: х ₁ = х ₂ = х ₄ = 1, х ₃ = 0; оптимальное значение критерия равно 10.

При реализации алгоритма B _кзр число записей в каждом из составляемых списков Sⁱ, i = 1,..., n, не превышает С ^(!) + 1 (действительно, в любом из этих списков нет двух записей с одинаковым значением второй компоненты, которое всегда целочисленно и принадлежит отрезку [0, С ^(!)]). Отсюда получаем, что в каждом несокращенном списке Rⁱ имеется не более 2(С ^(!) + 1) записей. Каждый список Rⁱ составляется по списку S^{i –1} выполнением линейно зависящего от количества записей в списке S^{i –1} числа элементарных операций. При переходе от несокращенного списка Rⁱ к списку Sⁱ число выполняемых элементарных операций по верхней оценке квадратично зависит от количества записей в Rⁱ. Получаем, что число элементарных операций, выполняемых при получении каждого следующего списка имеет верхней оценкой функцию, квадратично зависящую от С ^(!). С учетом того, что последним составляемым является список Sⁿ, получаем в качестве оценки числа выполняемых алгоритмом B _кзр элементарных операций kn (С ^(!))², здесь k – константа, не за-висящая от значений n и С ^(!). Если максимальная из стоимостей предметов равна с*, то С ^(!) не превосходит nс* и в качестве верхней оценки временной вычислительной сложности изложенного алгоритма мы получаем kс*n ³.

Через К ^ст[ Q ] обозначим подкласс задач о ранце с n предметами, в которых стоимость каждого предмета не превосходит Q (n), здесь Q (n) – некоторая полиномиальная монотонно возрастающая функция от одной переменной. На задачах этого под-класса алгоритм B _кзр дает верхнюю оценку числа выполняемых элементарных операций kQ (n) n ³. Получаем, что задачи любого подкласса К ^ст[ Q ], где Q (n) – произвольная полиномиальная монотонно возрастающая функция от одной переменной, разрешимы в полиномиальном времени.