0,0
рейтинг
13 мая 2014 в 18:38

Разработка → Алгоритм решения задачи о рюкзаке ( версия 2, исправленная) из песочницы

Ниже приведен алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно несколько проще алгоритма динамического программирования (ДП).

Причина побудившая автора к публикации


Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:
Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.
Тем не менее я решил ознакомить сообщество с алгоритмом, т.к. в известных мне учебниках по дискретной математике я его не обнаружил (возможно плохо искал). В первой версии алгоритма была ошибка, указанная мне пользователем wataru. За это ему большое спасибо. Я постарался эту ошибку устранить. До алгоритма я дошел самостоятельно, так что надеюсь ничьих прав не нарушаю. Возможно кому нибудь описание будет интересно и пригодится.

Введение


Задача о одномерном рюкзаке (0-1 knapsack) является классической задачей дискретной оптимизации [1],[2]. Данная задача и ее варианты широко используются для моделирования большого числа практических задач. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Более точно, пусть P(i) > 0 и W(i) > 0 – соответственно стоимость и вес i-го предмета, где i = 1,2,3,…,N , а N– число предметов.
Требуется найти такой булев вектор X размерностью N, где
X(i) = 1, если предмет с номером i положен в рюкзак;
X(i) = 0, если предмет с номером i не положен в рюкзак;
чтобы была максимальной сумма Σ P(i) X(i)
и выполнялось неравенство Σ W(i) X(i) ≤ C, где C > 0 – вместимость рюкзака.
Существуют различные точные и приближенные алгоритмы решения задачи о рюкзаке.
К точным алгоритмам относятся:
  • полный перебор
  • метод ветвей и границ
  • динамического программирования (ДП)
.
Приближенными алгоритмами являются жадный (ЖА) и генетический (ГА). Сравнение различных методов решения задачи о рюкзаке широко представлено в литературе и интернете, поэтому не будем на нем останавливаться и сразу перейдем к делу.Предлагаемый ниже алгоритм можно условно рассматривать как усложнение ЖА и как упрощение алгоритма ДП.
Рассмотрим вариант алгоритма решения задачи о рюкзаке при условии, что веса предметов являются натуральными числами, а стоимости предметов являются вещественными числами.

Описание алгоритма решения задачи о рюкзаке с элементами псевдокода


INPUT: // Входные данные
Массивы исходных данных (ИД) содержат целые веса W и вещественные стоимости P предметов W(1...N) > 0 и P(1...N) > 0
где N число предметов и C > 0 – вместимость рюкзака.
OUTPUT: // Выходные данные
Булев массив X(1...N), где X(i) = 1, если предмет с номером i входит в решение, и X(i) = 0, если предмет с номером i не входит в решение.

START // начало алгоритма

Этап 1 // сортировка ИД
Сортируем ИД в порядке уменьшения удельной стоимости предметов:
P(1) / W(1) >= P(2) / W(2) >= ...>= P(i) / W(i)>=… >= P( N) / W(N)
где P(i) > 0 стоимость предмета i , W(i) >0 вес предмета i.
В массиве X(1...N) все элементы первоначально = 0.
Для снижения потребности в памяти для алгоритма определяем минимальный вес в наборе ИД W_min = min( W )

Этап 2 // инициализация рабочих массивов
Создаем массив вещественных чисел LP размерностью (W_min… С)
и массив целых чисел LCr размерностью (W_min… С) . Заносим в массив LP и LCr данные первого элемента из отсортированного списка ИД
  LP( W(1) )  = P(1)
  LCr( W(1) ) = 1 
где P(1) стоимость и W(1) вес первого предмета в отсортированном списке ИД.

Этап 3 // заполнение рабочих массивов
 FOR i = 2 TO N  // цикл по оставшимся элементам ИД  

Пусть W(i) и P(i) вес и стоимость текущего элемента ИД.
Создаем пустой массив вещественных чисел Clone размерностью (W_min… С).
Вносим в массив Clone стоимость текущего элемента ИД
Clone( W(i) ) = P(i)
.
Копируем в массив Clone ненулевые данные из массива LP добавляя стоимость P(i) текущего элемента и увеличивая его индекс на его вес W(i), при условии что индекс в Clone не превзойдет вместимости рюкзака C.
FOR j = W_min TO ( C - W(i) )  
  IF LP(j) >0 THEN
    Clone( j + W(i) ) = LP(j) + P(i) 
  END IF
NEXT // конец цикла копирования 

Проводим модификацию массивов LP, LCr на основе данных массива Clone. Обновляем в массивах LP,LCr только те элементы стоимость которых в Clone больше чем в LP.
  FOR j = W_min TO C  
    IF Clone( j ) >0 AND Clone( j ) > LP( j ) THEN
       LP( j ) = Clone( j ) 
       LCr( j ) = i
     END IF
   NEXT  // конец цикла модификации LP, LCr  
NEXT  // конец цикла по оставшимся элементам 

Этап 4 // формирование результата, обратный спуск
В массиве LP находим максимальное значение стоимости Pmax = MAX( LP ), это стоимость найденного оптимального решения. Индекс найденного в массиве элемента равен весу решения, обозначим его Wr, т.е. LP( Wr) = Pmax. Внесем первый найденный элемент в X:
 X( LCr( Wr ) ) = 1 
далее
// цикл формирование результата 
UNTIL Wr > 0 // если Wr = 0, результат сформирован  
 // уменьшаем вес решения на вес добавленного в результат предмета
  Wr = Wr - W( LCr( Wr ) )   
  // Проверяем, не внесен ли уже следующий элемент в  X 
  IF  X(LCr( Wr ) = 0 then  // не внесен
       X( LCr( Wr ) ) = 1   //  вносим
  ELSE  //   внесен  

Выходим из цикла UNTIL и повторяем этапы 2, 3, 4 ( только на этапе 2 массивы LP, LCr не создаем, a заполняем нулями ). Повторять этап 1 (сортировка ИД) не нужно. Это по существу рекурсия, но из за предварительной сортировки ИД, она будет не глубокой. На некоторых наборах ИД рекурсии вообще может не быть. При повторе расчетов рассматриваем только те ИД, индекс которых меньше LCr( Wr ) и снижаем требуемый размер рюкзака до достигнутого веса Wr.
         N_NEW = LCr( Wr ) -1
         C_NEW = Wr
         GOTO этап 2
    END IF
NEXT // конец цикла формирование результата 

FINISH // конец алгоритма
Стоимость найденного решения Σ P(i) X(i), вес Σ W(i) X(i).
Правильность расчета итоговой стоимости рюкзака легко доказывается по индукции. Восстановление оптимального набора предметов, тоже не вызывает затруднений. Представленный алгоритм позволяет получить точное решение целочисленной задачи о рюкзаке.

Итоговые замечания


  1. Общая сложность представленного алгоритма складывается из сложности сортировки ИД и сложности выполнения этапа 3 алгоритма (с учетом числа итераций). Время работы этапа 3 пропорционально числу предметов на вместимость рюкзака (N * C). Заранее определить число итераций достаточно сложно. Число итераций может варьироваться от 0 до числа предметов в решении Σ X(i). При каждой итерации возникающей на этапе 4 объем вычислений на этапах 2, 3 уменьшается. Верхняя оценка временной сложности всего алгоритма не превышает N * C * ( число итераций + 1)
  2. Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
  3. Внутренние циклы этапа 3 легко выполняются параллельно.
  4. При большом разбросе удельной стоимости предметов, если на этапе 3 алгоритма в верхней части массива LP перестают происходить изменения, можно прерывать этап 3 и не рассматривать оставшиеся предметы с низкой удельной стоимостью.
  5. Если вместимость рюкзака С, достаточно велика, так что массивы размерности С не могут быть созданы по техническим причинам или веса предметов являются вещественными числами, то предложенный алгоритм может быть легко модифицирован заменой массивов связанными списками.
  6. Является ли данный алгоритм полиномиальным или нет, я не берусь судить.


Литература

  1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985.
  2. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ. М.: Издательский дом «Вильямc», 2005.
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (32)

  • +18
    — Ваш алгоритм не полиномиальный, а только псевдополиномиальный, потому что в оценку сложности входит емкость рюкзака, которая может быть задана сколь угодно большой, например 10^100.
    — В статье в википедии упоминается об алгоритме с аналогичными свойствами:
    This solution will therefore run in O(nW) time and O(nW) space. Additionally, if we use only a 1-dimensional array m[w] to store the current optimal values and pass over this array i+1 times, rewriting from m[W] to m[1] every time, we get the same result for only O(W) space.
    • +8
      Тут проблема та же, что и с факторизацией. Т.е. да, чтобы найти множители числа N нужно всего-то сделать N делений — дайте мне премию Тьюринга! Но интересует нас алгоритм, полиномиальный отностительно количества бит в числе, и из-за этого вся путаница. В случае задачи о рюкзаке мозг выносит еще сильнее.
      • 0
        Прошу прощения, разве не ceil( N / 2 )? (каждое деление даёт пару чисел [делитель; частное], оставшиеся решения — те же пары в другом порядке)
        • 0
          Скажу больше. Достаточно до sqrt(N). Т.к. пускай существует число a > sqrt(N), на которое нацело делится N. Тогда возможны два варианта, либо N/a = b >sqrt(N), либо N/a=b <=sqrt(N). Первый случай невозможен, а во втором мы просмотрели бы уже число b, пробегая до sqrt(N).
        • +3
          Все равно N/2 = O(N) = O(2^k), Где k — длина входных данных (количество бит).
    • 0
      Я согласен c вами, просто для задачи о рюкзаке обычно неявно подразумевается, что емкость рюкзака С значительно меньше чем сумма весов. т.е. для бесконечной емкости рюкзака в него попадут все предметы. Самый тяжелый вариант когда емкость рюкзака С = Σ W / 2.Логика алгоритма рассчитана на стандартные типы данных, например:
      long От -922 337 203 685 477 508 до 922 337 203 685 477 507
      double От -1,797 693 134 862 32e308 до 1,797 693 134 862 32e308
      Если C в них попадает, то все хорошо. Для очень больших C в пределах стандартных типов данных вместо массивов можно использовать списки и сложность тогда не будет явно зависеть от C, а скорее от длины списка.
      Если для записи C не хватает стандартных типов данных, то все плохо.
  • 0
    Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.


    Никогда не слышал о ДП-методе решения задачи о рюкзаке не за O(C) памяти. Как это делается?
    • 0
      Формально, в динамике нужен двумерный массив размера N*C. Но это можно очевидно реализовать или храня только 2 строчки массива, или пересчитывая его на месте в одномерном массиве размера C. Это так просто в реализации, что двумерность параметров вспоминается, разве что, при доказательстве корректности алгоритма.
      • 0
        Нет, понятно, что можно хранить данные гораздо дольше, чем алгоритму требуется и так можно любой алгоритм сделать плохим по памяти. Вот если бы всю матрицу можно было бы как-то использовать при восстановлении множества — тогда я бы согласился, что алгоритм требует столько памяти.
    • 0
      насколько мне известно, при решении задачи о рюкзаке методом ДП требуется двухмерный массив размера N * C, т.к. требуется восстановить решение. Возможно в методе ДП можно уменьшить двухмерного размерность массива, но видимо за счет дополнительных вычислений
      • 0
        В вашем методе тоже требуется двумерный массив для восстановления ответа. То, что написано у вас не работает. Контрпример я привел в комментарии ниже.
        • 0
          Извините, метод работает, я его проверял на нескольких десятков примеров, хотя это и не доказательство. Приду домой проверю ваш пример и отпишу, если хотите вышлю вам exe ( на VB6) Доказательство правильности состоит из двух этапов
          1 в результирующем массиве всегда будет максимальная стоимость, доказывается по индукции.
          2 результат восстанавливается по одномерному массиву, именно из за предварительной сортировки
          • 0
            Доказательство стоимости не надо, это очевидно. А вот второй пункт не верен.
            Пример ниже совсем простой (С=7, W={3,5,2}, P={15,20,6}). В комментарии ниже я подробно разобрал, что происходит.

            Вкратце, сортировка не спасает и массив LCr перезаписывается на более поздних итерациях.
      • 0
        Вот было бы как раз интересно узнать, чем же таким надо заполнить этот двухмерный массив, чтобы его надо было хранить целиком, чтобы восстановить ответ. Мне приходит в голову только искусственные схемы типа хранить в ячейке там 1 если для данной стоимости и данного номера объекта существует поднабор заданной стоимости, который может содержать объекты с номером не больше данного и обязательно содержит объект с данным номером.
  • +8
    Странно, этот алгоритм и есть динамическое программирование. Может, не самая каноническая реализация решения задачи о рюкзаке, но абсолютно той же сложности и по времени и по памяти. Если стандартную динамику реализовывать лениво (снизу вверх), будет практически тоже самое.

    У вас массив LP[j] на i-ой итерации — это максимальная стоимость подмножества первых i элементов весом j. LCr[j] — последний элемент в таком множестве. В стандартной динамике те же самые параметры и массивы.

    Сортировка объектов по удельной стоимости и введение дополнительного массива Clone действительно являются эвристиками, позволяющими немного ускорить решение в некоторых случаях. Но от этого алгоритм не становится принципиально лучше динамики.
    • 0
      Становится. В каноничной реализации (по крайней мере, той, которую я считаю «каноничной») нам требуется O(nw) времени и столько же памяти. Здесь же память линейна, за счёт того, что мы для каждого веса храним только один способ его получить. При этом алгоритм хуже не становится — мы по-прежнему можем, пользуясь линейной памятью, восстановить набор предметов.
      • +1
        Путаете. Не знаю, какую динамику вы имеете в виду, но при реализации стандартной динамики не надо хранить двумерный массив.
        В динамике считается L(i,j) — (самое дешевое подмножество из первых i объектов весом j). Пересчитывается очень просто L(i,j) = min(L(i-1,j), L(i-1, j-W(i))+C(i)). Достаточно хранить одну строку L(i, *), т.е. одномерный массив, и пересчитывать его с конца в начало.

        Никогда на практике не сталкивался с реализацией динамики с O(NC) памяти. Да, времени надо O(NC), но в вашем алгоритме точно такая же оценка сложности: цикл по i до N, внутри цикл по j до С-W(i). Эвристики раннего завершения этапа 3 не влияют на оценку сложности ни в среднем ни в худшем случае. Параллелизация, которая доступна использовании дополнительного массива Clone тоже ускоряет алгоритм в несколько раз, не влияя на оценку сложности.
  • 0
    «почему в учебниках по дискретной математике этого алгоритма нет»

    Ну, тут есть, и я разбираю его со студентами, как пример практичного алгоритма, при определенных условиях для которого можно доказать полиномиальность в среднем.
    • 0
      PDF Кузюрина и Фомина я читал, но описания такого алгоритма не нашел. Видимо или PDF не тот, или искал плохо. Я писал в начале, что алгоритм уже известен, а всех книг по ДМ мне не прочитать.
      • 0
        Вот конкретно слайды и видеолекция с анализом в среднем алгоритма Н-У. Ну или на 145-й странице книги.

        • 0
          При всем моем уважении к вам и к Кузюрину, описания алгоритма на стр. 145 и ниже нет, там есть доказательство теоремы 12. Параграф называется
          «Рюкзак»: полиномиальность в среднем
          Есть ссылка на алгоритм 25 (Н-У) стр. 108, и далее ссылка на стр. 106 где приведен «стандартный» алгоритм ДП. Также я нигде не обнаружил предварительной сортировки ИД по уменьшению удельной стоимости, что является важной частью описанного в топике алгоритма.
  • 0
    А где почитать о задаче, где описаны геометрические размеры рюкзака (это может быть куб или паралелепипед) и вещей, которые тоже могут быть кубами и паралелепипедами и имеют разную ценность.?

    Суть в том, что каждую вешь можно разместить в рюкзаке шестью разными способами, ну там лёжа на одной из трех граней, и под углом 0/90 градусов
    • 0
      это одномерный рюкзак, веса складываются, например 3 кг яблок + 2 кг апельсинов = 5 кг. Двухмерные и трехмерные упаковки это значительно сложнее. В квадрат 10 на 10 можно поместить прямоугольник 9 на 8, а 12 на 2 — нельзя. Насколько мне известно, для решения 2-3 мерных задач используются эвристики и ГА.
    • 0
      на хабре!
      habrahabr.ru/company/infostart/blog/217369/
      брут-форс решение задачи о рюкзаке с помощью SQL. Только без учета ценности, но мне кажется, это можно доработать.
  • +13
    Кстати, ваш алгоритм не правильно восстанавливает ответ.
    Пусть веса объектов = {3, 5, 2}, а стоимости = {15, 20, 6}

    Удельные стоимости = {5, 4, 3}
    Пусть вместимость рюкзака С=7.
    Итак, оптимальный набор, очевидно, последние 2 объекта (первые 2 просто в рюкзак не помещаются). И вы их найдете. Стоимость в ответе будет 26.
    А вот с восстановлением ответа у вас будут проблемы.

    Перед циклом массивы будут
    LP = {0, 0,0,15,0,0,0,0} // LP[3] == 15
    LCr = {0, 0, 0, 1, 0, 0, 0, 0} // LCr[3] == 1

    На первой итерации (i=2):
    Сначала Сlone[5] станет 20
    Затем в цикле по j мы ничего не найдем, т.к. С-W[i] = 7-5 = 2. А LP только в 3-ем элементе не 0.
    После первой итерации массивы будут
    LP = {0, 0, 0,15,0,20,0,0} // LP[5] == 20
    LCr = {0, 0, 0, 1, 0, 2, 0, 0} // LCr[5] == 2

    И, наконец, на последней итерации:
    Сначала Сlone[2] станет 6.
    В цикле по j от 2 до 5 мы найдем оба ненулевых LP.
    Сделаем Clone[3+2] = Clone[5] = 15+6=21
    Сделаем Clone[5+2] = Clone[7] = 20+6=26

    после цикла по j, на мы перепишем LP[5] на 21 вместо 20 (испортив при этом LCr, который будет нужен при восстановлении ответа) и запишем LP[7]
    Итоговые массивы будут:
    LP = {0, 0, 0,15,0,21,0,26} // LP[5] == 21, LP[7] ==26
    LCr = {0, 0, 0, 1, 0, 3, 0, 3} // LCr[5] == 3, LCr[7] ==3

    При восстановлении ответа, мы найдем LP[7]=26, как ответ. Восстановим 3-ий объект, получим Wr=5. Но нужный нам LCr[5] был неправильно перезаписан на 2-ой итерации, и мы опять берем 3-ий объект, получив Wr=3. В итоге мы получим множество {3,3,1}, что не правильный ответ.

    Нельзя обойтись одномерным массивом для восстановления ответа. Вы, видимо, думали, что сортировки по удельному весу будет достаточно, чтобы никогда нужный нам LCr не перезаписывался более поздними итерациями, но это не так. Если будете пытаться исправить алгоритм, убедитесь что он работает на примере с такими же предметами, но C=5 и С=8. В зависимости от размера рюкзака нам надо или нельзя перезаписывать LCr на более поздних итерациях.

    Можно было бы попытаться хранить в LCr список всех возможных подмножеств, но такой подход очень быстро даст O(C*2^n) памяти.

    • +2
      Вы правы, предложенный мной алгоритм содержит ошибку. Восстановить состав рюкзака с помощью одномерного массива LCr возможно не всегда. Ваш пример это доказывает. Первоначально LCr и был двухмерным ( C на N), но потом мне показалось что LCr можно сделать одномерным и сэкономить память, что даст алгоритму преимущество над методом ДП. Ошибся. Предлагаю дальнейшее обсуждение топика прекратить. Проверял алгоритм на разных наборах данных, вроде результаты получались правильные. Хорошее подтверждение тому, что экспериментальный метод в математике не работает.
      • +1
        Да, к сожалению, единственный метод — это формальное доказательство правильности алгоритма. Или проверить на всех возможных входных данных, что почти всегда невозможно.

        Наверно стоит изменить топик — дописать какой-то UPD или вообще убрать его в черновики.
        • 0
          есть, определенная мысль как исправить расчет LCr оставив его одномерным, надеюсь исправить топик, но надо немного времени. Формально доказать правильность алгоритма тоже не просто.
  • 0
    Впервые услышал о данном алгоритме при просмотре сериала Числа, советую всем посмотреть, математикам в особенности!
  • 0
    Не совсем понял, что происходит во второй версии алгоритма. То, что цена ответа будет правильной опять очевидно. Как восстанавливается набор элементов я не совсем понял.

    Верно ли, что во время восстановления ответа, если видно, что надо взять уже взятый элемент, то восстановление останавливается и вы рекурсивно решаете задачу уже исключив взятые ранее элементы?
    • 0
      Видимо, у вас не правильная оценка сложности. Сложность вашего алгоритма не (N*C)^K, где K — количество итераций, а N*C*K.
      Все еще непонятно, почему безопасно брать все объекты до первого противоречия на этапе 4. Может быть, что вы случайно восстановите не нужный объект до того как найдете противоречие.

      Но ваш алгоритм можно чуть чуть упростить и тогда все будет точно и легко доказано. Надо брать только один последний объект (LCr[Wr]) и затем снова возвращаться к этапу 2. Очевидно, что эта запись в массиве LCr не может быть переписана чем-то позже. Она и так последняя. Этот последний объект точно есть в ответе. Оценка сложности такого алгоритма будет N*C*N.

      В целом ваша идея разменять большую потребность в памяти на более медленный алгоритм очень удачна.

      Даже без этого упрощения сложность алгоритма остается такой же, т.к. итераций может быть сравнимо с N (их будет N/3 если взять и расширить мой указанный где-то в этой теме контр пример к первой версии алгоритма).

      Советую вам или привести формальное доказательство корректности восстановления ответа, или изменить алгоритм, чтобы на каждой итерации (этапы 2,3,4) восстанавливать только один объект из ответа.
      • 0
        Извиняюсь за задержку с ответом, был на даче. То что в указанном алгоритме на первой итерации значение LCr на максимуме LP будет правильно — очевидно. После сдвига вниз на вес найденного элемента мы или находим элемент существующий в Х или находим новый элемент не существующий в Х.
        Во втором случае мы продолжаем спускаться вниз ( как и было в первой версии алгоритма) ничего не пересчитывая ( LP , LCr).
        Первый случай возникает тогда, когда место, откуда мы прыгнули в максимум перезаписалось уже существующим в решении элементом. Тогда мы идем в рекурсию и снижаем число рассматриваемых элементов ИД + снижаем размер рюкзака. Из за предварительной сортировки по убыванию удельной стоимости необходимость в рекурсии будет не всегда ( например при попадании в точки, в которых LCr не изменялась). Вот если бы ИД были отсортированы по возрастанию удельной стоимости элементов, то на рекурсию мы бы попадали (наступали) почти на каждом шагу.
        С вашей верхней оценкой временной сложности не более N*N*C согласен ( теоретически видимо возможен вариант ИД, когда итерацию будем делать на каждом шаге), со степенью я намудрил. Тем не менее, существуют наборы данных на которых итераций нет вообще и временная сложность =N*C. Как часто бывает, сложность алгоритма зависит от ИД.
        Прошу не судить строго мои рассуждения, но мне кажется в алгоритме менять ничего больше не надо. Модифицировать алгоритм могут делать все желающие, желательно в лучшую сторону.
        Я видимо не смогу формально доказать правильность восстановления решения на этапе 4. Я просто поделился алгоритмом, который требует меньше памяти чем стандартный алгоритм ДП в N раз или его потребность в памяти не зависит от N и применим в случае когда веса элементов вещественные, а не целые числа.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.