Задача о ранце

Поделись знанием:
(перенаправлено с «Укладка рюкзака»)
Перейти к: навигация, поиск

Задача о ранце (или задача о рюкзаке) — одна из NP-трудных задач комбинаторной оптимизации. Своё название получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о ранце можно столкнуться в экономике, прикладной математике, криптографии и логистике.

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.





Классическая постановка задачи

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. Также имеется рюкзак определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.

Математически задачу можно сформулировать так: имеется <math>n</math> грузов. Для каждого i-го груза определён вес <math> w_i>0 </math> и его ценность <math>v_i>0</math>, <math>i= 1,2,...,n</math>. Максимальный суммарный вес предметов в рюкзаке задаётся грузоподъёмностью <math>W</math>. Необходимо

максимизировать <math>\sum_{i=1}^n v_i x_i</math>
с ограничениеми <math>\sum_{i=1}^n w_i x_i \leq W</math> и <math>x_i \in \{0,1\}</math> [1].

Варианты задачи о ранце

Существует множество разновидностей задачи о ранце, в зависимости от условий, наложенных на рюкзак, предметы или их выбор.

  1. Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[2]: не более одного экземпляра каждого предмета.
  2. Ограниченный рюкзак (англ. Bounded Knapsack Problem)[3]: не более заданного числа экземпляров каждого предмета.
  3. Неограниченный рюкзак (англ. Unbounded Knapsack Problem)[3]: произвольное количество экземпляров каждого предмета.
  4. Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[4]: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
  5. Мультипликативный рюкзак (англ. Multiple Knapsack Problem)[5]: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
  6. Многомерный рюкзак (англ. Multy-dimensional knapsack problem): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна[4].
  7. Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem): суммарная ценность задается неотрицательно определенной квадратичной формой[6].

Наглядная интерпретация задачи о ранце привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в криптографии. В одной из работ по вычислительной лингвистике[7] предложена формулировка задачи автоматического реферирования текстов (англ.), частный случай которой соответствует постановке задачи о ранце.

Приложения

Доподлинно неизвестно, кто первым привел математическую формулировку задачи о ранце. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса (англ.)[8][9], датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem»[10], особенно в 70-90-е годы 20-го века, как теоретиками, так и практиками[2]. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список К. Мэннига NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»)[11].

На основе задачи о ранце был создан первый алгоритм асимметричного шифрования. Впервые идея криптографии с открытыми ключами была представлена Уитфилдом Диффи и Мартином Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference)[12][13].

Также задача о рюкзаке может служить моделью для большого числа промышленных задач[2][14]:

  • Размещение грузов на складе минимального размера.
  • Раскройка ткани — из имеющегося куска материала получить максимальное число выкроек определенной формы.
  • Расчет оптимальных капиталовложений.

Задача о ранце в криптографии

Криптосистема Меркла — Хеллмана — первый основанный на задаче о ранце алгоритм для обобщённого шифрования с открытым ключом. Разработан Ральфом Мерклом и Мартином Хеллманом в 1978 году. Был опубликован одностадийный (англ. singly-iterated) и мультистадийный варианты (англ. multiply-iterated). Алгоритм мог быть использован только для шифрования, но Ади Шамир адаптировал его для использования в цифровых подписях[15].

В дальнейшем было предложено как множество модификаций криптосистемы Меркла — Хеллмана, так и совершенно новых криптосистем на основе задачи о ранце. Среди них[16]:

  1. Рюкзак Грэм — Шамира
  2. Рюкзак Гудмана — Макколи
  3. Рюкзак Накаше — Штерна
  4. Рюкзак Шора — Ривеста

Шифрование с помощью задачи о ранце

Сообщение шифруется как решение набора задач о ранце[15].

Определение. Рюкзачным вектором <math> A = (a_1,...,a_n)</math> назовём упорядоченный набор из n предметов, где <math> a_i</math> - вес <math> i</math>-го предмета[17].

Для шифрования открытого текста его разбивают на блоки длиной <math>n</math> бит (например, открытый текст <math>(1 1 1 1 0 0)</math> соответствует наличию четырёх из шести возможных предметов в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие.

После этого считается суммарный вес предметов в рюкзаке, и он передаётся в качестве шифротекста.

Пример шифрования данным алгоритмом:

Пусть задан рюкзачный вектор <math> A = (3\ 4\ 6\ 7\ 10\ 11)</math> с длиной <math>n=6</math>.

Открытый текст 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Вещи в рюкзаке 3 4 6 7 10 6 7 11
Шифротекст 3 + 4 + 6 + 7 + 10 = 30 6 + 7 = 13 0 11

Для заданного <math>A</math> все криптосистемы есть числа, не превышающие 41, то есть суммарный вес всех предметов в рюкзачном векторе.

На практике, для шифрования необходим сверхвозрастающий рюкзак, то есть элементы упорядоченного рюкзачного вектора должны являться сверхвозрастающей последовательностью. В таком случае для каждого исходного текста существует единственный шифротекст[18]. В указанном примере рюкзак не является сверхвозрастающим — можно получить одинаковый шифротекст для векторов 100010 и 001100.

Решения задачи

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

Точные решения

Полный перебор

Пусть в рюкзак загружаются предметы <math> N </math> типов. Рассмотрим задачу, когда каждый предмет имеется в единственном экземпляре. Нужно определить максимальную стоимость груза, вес которого не превышает <math> W </math>. Для получения решения алгоритмом полного перебора осуществляется перебор всех вариантов загрузки рюкзака. Временная сложность алгоритма <math> O(N!) </math>, т.е он работоспособен для небольших значений <math> N </math>[19]. С ростом <math> N </math> задача становится неразрешимой данным методом за приемлемое время.

На рисунке показано дерево перебора для четырёх предметов. Корень дерева соответствует пустому рюкзаку, в кружках показан номер предмета. Первый предмет возможно выбрать четырьмя способами, второй тремя и т. д.

После составления дерева, необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает <math> W </math>[20].

Метод ветвей и границ

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

Пусть есть оптимальное решение <math> R </math>. Попытаемся его улучшить, рассмотрев решение на другой ветви. Если на рассматриваемой в данной момент ветви решение становится хуже (с какого-то шага), чем <math> R </math>, то прекращаем его исследование и выбираем другую ветвь дерева[21].

Пусть для предыдущего четырёхуровневого дерева есть ограничение <math>W=5</math>, а вес предмета соответствует его номеру. Тогда, применяя метод ветвей и границ, можно сократить количество вариантов для перебора с 24 до 8, как показано на рисунке.

Применение метода ветвей и границ

Метод ветвей и границ можно изобразить следующим образом: на двумерной плоскости по оси <math> X </math> откладывается количество предметов, по оси <math> Y </math> — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось <math> Y </math> равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета[22].

Таким образом, любому решению задачи соответствует некоторый путь в построенном дереве. Задача сводится к нахождению пути максимальной длины[22]. Пример. Пусть вместимость рюкзака <math> W=14 </math>.

Номер предмета Ценность Вес
1 3 5
2 5 10
3 4 6
4 2 5

На рисунке в квадратных скобках [] стоит суммарная ценность на каждом шаге алгоритма. Видно, что для оптимального решения она равна 7. Такж

Методы динамического программирования

Задача об неограниченном рюкзаке

При дополнительном ограничении на веса предметов, задачу о ранце можно решить за псевдополиномиальное время методами динамического программирования.

Пусть вес каждого предмета <math>w_i</math> является целым неотрицательным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех <math>w \in \Z: 0 <= w <= W</math>, где <math>W</math>- заданная грузоподъемность. Определим <math>m[w]</math> как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью <math>w</math>.

Для <math>m[w]</math> нетрудно записать рекуррентные формулы:

  • <math>m[0]=0</math>
  • <math>m[w]= \max_{w_i \le w}(v_i+m[w-w_i])</math>[23],

где <math>v_i, w_i</math> - ценность и вес <math>i</math>-го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения <math>m[w]</math>, начиная с <math>0</math> и до <math>W</math>[23]. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.

Так как на каждом шаге необходимо найти максимум из <math>n</math> предметов, алгоритм имеет вычислительную сложность <math>O(nW) </math>. Поскольку <math>W</math> может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. По этому эффективность данного алгоритма определяется значением <math>W</math>. Алгоритм даёт отличные результаты при <math>W \leq 1000</math>, но не очень хорошие для <math>W \geq 10\ 000\ 000</math>[24].

Задача об рюкзаке 0-1

Решение задачи о рюкзаке 0-1 близко к решению предыдущей задачи, но необходимо учесть тот факт, что каждый предмет имеется в единственном экземпляре. Пусть <math>m[w , i]</math> - максимальная ценность предметов, полученных из первых <math>i</math> имеющихся предметов, с суммарным весом не превышающим <math>w</math>.

Рекуррентные соотношения:

  • <math>m[0 , w]=0</math>
  • <math>m[i,\,w]=m[i-1,\,w]</math>, если <math>w_i > w</math>
  • <math>m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)</math>, если <math>w_i \leq w</math>
Вычисляя <math>m[n , W]</math>, можно найти точное решение. Если массив <math>m[i , w]</math> помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных[23].
// Ввод:
// Ценности предметов (загруженные в массив v)
// Веса предметов (загруженные в массив w)
// Количество предметов (n)
// Грузоподъемность (W)

for j from 0 to W do:
    m[0, j] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
Динамическое программирование над ценностями предметов

Обозначим за <math>y[i, V]</math> минимальный вес предметов, суммарной ценностью <math>V</math>, полученных из первых <math>i</math> имеющихся предметов. Если необходимый вес получить невозможно, положим <math>y[i, V] = W+1</math>. Максимальную ценность предметов для каждого <math>i</math> получим при помощи жадного алгоритма.

После этого решим функциональное уравнение динамического программирования:

<math>y[i, V] = \begin{cases} y[i-1, V], & \text{if } V < v_i \\ \min\{\ y[i-1, V], y[i-1, V-v_i]+w_i\}, & \text{if }V \geq v_i \end{cases}</math>,

с начальными условиями:

<math>y[0, 0]=0</math>

<math>y[0, V]=W+1</math>[25]

Приближенные решения

Как и для большинства NP-полных задач, не всегда необходимо получать точное решение, так как решения, близкие к оптимальным, могут применяться в прикладных задачах.

Жадный алгоритм

Согласно жадному алгоритму предметы сортируются по убыванию стоимости единицы веса каждого. В рюкзак последовательно складываются самые дорогие за единицу веса предметы из тех, что помещаются внутри[26].

Сложность сортировки предметов <math> O(N\log(N)) </math>. Далее происходит решение о помещении каждого предмета в рюкзак за <math> O(N) </math>[26]. Итоговая сложность <math> O(N\log(N)) </math>.

Пример. Пусть вместимость рюкзака <math> W=80 </math>. Предметы уже отсортированы. Применим жадный алгоритм.

i вес цена цена/вес
1 15 60 4
2 30 90 3
3 50 100 2

Кладём в рюкзак первый предмет, а за ним второй. Третий предмет в рюкзак не влезет. Суммарная ценность вещей в рюкзаке равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190.

Впервые жадный алгоритм был предложен Джорджом Даницгом[27] для решения задачи о неограниченном рюкзаке. Тем не менее, решение жадным алгоритмом проблемы рюкзака 0-1 может быть далеко от оптимального, как показано выше.

Если бы количество каждого предмета было бы неограниченно, то оптимальным решением было бы взять 5 первых предметов с общей ценностью 300. Такое же решение даёт жадный алгоритм.

В худшем случае, ценность в решении, полученного жадным алгоритмом, может составлять только 50% от ценности в оптимальном решения[26].

Приближенная схема полностью полиномиального времени

Возникает естественная задача, получить полиномиальное решение с гарантированной точностью <math>1-\varepsilon</math>. Для этого существует целый ряд приближенных схем полностью полиномиального времени, то есть со сложностью, являющейся полиномом от <math>n</math> и <math>\frac{1}{\varepsilon}</math>.

Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом[25]:

  1. Найдем приближенное решение <math>x^l</math> при помощи жадного алгоритма. Пусть <math>x^*</math> - точное решение. Тогда из оценки эффективности жадного алгоритма <math>x^l \leq x^* \leq 2x^l</math>.
  2. Отмасштабируем ценности следующим образом: <math>v'_i = \left \lfloor \frac{v_i}{\frac{z^l\varepsilon}{n}} \right \rfloor</math>.
  3. Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение.

Существует множество различных схем апроксимации. Тем не менее, они сильно зависят от формулировки задачи о ранце. Например, если в условии появляется второе ограничение типа неравенства (духмерный рюкзак), то задача уже не имеет известной схемы полиномиального времени[28].

Генетические алгоритмы

Как и для других NP-трудных задач оптимизации, для решения задачи о ранце применяются генетические алгоритмы. Они не гарантируют нахождения оптимального решения за полиномиальное время и не дают оценку близости решения к оптимальному, но обладают хорошими временными показателями, позволяя найти "достаточно хорошее" решение быстрее других известных детерминированных или эвристических методов.[29]

Каждая особь(генотип) представляет собой подмножество предметов, которые мы хотим упаковать в ранец (их общий вес может превысить допустимую грузоподъемность). Для удобства, информация хранится в виде бинарных строк, в которых каждый бит определяет, помещается ли этот предмет в ранец[30].

Функция приспособленности определяет близость решения к оптимальному. Например, таковой может служить суммарная ценность предметов, при условии, что суммарный вес не превосходит грузоподъемность.

После серии смен поколений, в которых скрещиваются наиболее приспособленные особи и игнорируются оставшиеся, алгоритм, по предположению, должен улучшить исходные решения[30].

Решение задачи о сумме подмножеств

Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть <math>W</math> - грузоподъемность рюкзака, <math>w_i</math>- вес <math>i</math>-го предмета, а его стоимость <math>v_i = w_i</math>. Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

<math>W = \sum_{i=1}^N w_i x_i, \qquad \ x_i \in \{0 , 1\}</math>

Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор <math>(x_1,..,x_n)</math>. В качестве функции приспособленности следует использовать близость суммарного веса предметов к <math>W</math>, с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем <math>W</math>)[30].

Определим формально функцию приспособленности <math>f(x_1,..,x_n): \{0,1\}^n \rightarrow \mathbb{R}</math>. Пусть <math>\mathcal{S}</math> - сумма весов всех предметов. Тогда <math display="inline">\Delta_{max} = max(W, \mathcal{S}-W)</math> - максимально возможное отклонение веса предметов в рюкзаке от <math>W</math>.

Пусть <math display="inline">W' = \sum_{i=1}^N w_i x_i</math> - суммарный вес предметов для данного вектора. Тогда положим:

<math>f(x_1,..,x_n) = \begin{cases} 1 - \sqrt{\frac{W-W'}{W}}, & W' \leq W, \\

1 - \sqrt{\frac{W'-W}{\Delta_{max}}}, & W' > W. \end{cases}</math>[30]

Пользуясь общим алгоритмом, можно найти приближенное решение:

  1. Создать случайный набор особей - популяцию.
  2. Подсчитать функцию приспособления для каждой особи.
  3. Оставить только наиболее приспособленных особей (естественный отбор).
  4. Произвести скрещивания особей.
  5. Подвергнуть потомков мутации.
  6. Продолжить со второго шага.

Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций[30].

Нелинейная задача о ранце

В общем виде, нелинейную задачу о ранце можно сформулировать следующим образом:

Пусть вектор <math>x = (x_1,..,x_n) \in \mathbb{R}^n</math> определяет количество экземпляров каждого предмета в ранце. Тогда задача состоит в нахождении минимума функции

<math>\min_{x \in S} \ f(x)</math>,

при заданном ограничении:

<math>g(x) \leq b </math>.

Функции <math>f(x) , g(x): \mathbb{R}^n \rightarrow \mathbb{R} </math> предполагаются непрерывными и дифференцируемыми на <math>\mathbb{R}^n</math>. <math> b </math> - целочисленная константа, множество <math>S </math> непусто[31].

В случае линейных функций <math>f(x) , g(x) </math>, задача сводится к одной из классических постановок, в зависимости от множества <math>S </math>:

  • <math>S = \{0 , 1\}^n

</math> - рюкзак 0-1

  • <math>S = \mathbb{N_0}^n

</math> - неограниченный рюкзак

  • <math>S = \{(x_1,..,x_n) \in \mathbb{N_0}^n : x_i \leq c_i\}

</math> - ограниченный рюкзак Свобода в выборе функций <math>f(x) , g(x) </math> позволяет решать более широкий класс задач, включая организацию производственных мощностей (англ.), оптимальное распределение семплов в районированной выборке или решение квадратичной задачи о ранце[31].

См. также

Напишите отзыв о статье "Задача о ранце"

Примечания

  1. Silvano, 1990, p. 1.
  2. 1 2 3 Silvano, 1990, p. 2.
  3. 1 2 Kellerer, Pferschy, Pisinger, 2003, p. 127.
  4. 1 2 Kellerer, Pferschy, Pisinger, 2003, p. 147.
  5. Silvano, 1990, p. 157.
  6. G. Gallo, P. L. Hammer, B. Simeone [link.springer.com/chapter/10.1007/BFb0120892 Quadratic knapsack problems] (англ.) // Mathematical Programming Studies. — 2009. — 24 февраль (vol. 12). — P. 132-149. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0303-3929&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0303-3929].
  7. Riedhammer et al, 2008, pp. 2436.
  8. G. B. Mathews [plms.oxfordjournals.org/content/s1-28/1/486.full.pdf On the partition of numbers] (англ.). — 1897. — P. 486-490.
  9. Kellerer, Pferschy, Pisinger, 2003, p. 3.
  10. Kellerer, Pferschy, Pisinger, 2003, p. 9.
  11. Р. Карп [www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems] (англ.). — 1972.
  12. Шнаер, 2002, p. 19.2.
  13. Габидулин, Кшевецкий, Колыбельников, 2011.
  14. Бурков, 1974, p. 217.
  15. 1 2 Шнаер, 2002, p. 19.1.
  16. Kin Ming Lai. [www.ics.uci.edu/~mingl/knapsack.html Knapsack Cryptosystems: The Past and the Future] (рус.). — 2001.
  17. Саломаа, 1995, p. 103.
  18. Саломаа, 1995, p. 104.
  19. Окулов, 2007, pp. 92-93.
  20. Окулов, 2007, pp. 101-105.
  21. Бурков, 1974, p. 225.
  22. 1 2 Новиков, 2001, p. 12.
  23. 1 2 3 Романовский И.В. Алгоритмы решения экстремальных задач. — Наука, 1977. — С. 252-259. — 352 с.
  24. Стивен С. Скиена. Алгоритмы. Руководство по разработке. — 2-e. — СПб: БХВ-Петербург, 2011. — С. 448-451. — 720 с. — ISBN 978-5-9775-0560-4.
  25. 1 2 Hans Kellerer, Ulrich Pferschy, David Pisinger. [link.springer.com/10.1007/978-3-540-24777-7 Knapsack Problems - Springer].
  26. 1 2 3 Martello S., Toth P. Knapsack problems: algorithms and computer implementations. — John Wiley & Sons Ltd., 1990. — С. 29,50. — 296 с. — ISBN 0-471-92420-2.
  27. George B. Dantzig [pubsonline.informs.org/doi/abs/10.1287/opre.5.2.266 Discrete-Variable Extremum Problems] // Operations Research. — 1957-04-01. — Т. 5, вып. 2. — С. 266–288. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0030-364X&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0030-364X]. — DOI:10.1287/opre.5.2.266.
  28. Ariel Kulik, Hadas Shachnai [www.sciencedirect.com/science/article/pii/S0020019010001626 There is no EPTAS for two-dimensional knapsack] // Information Processing Letters. — 2010-07-31. — Т. 110, вып. 16. — С. 707–710. — DOI:10.1016/j.ipl.2010.05.031.
  29. Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. [www.unn.ru/pages/e-library/aids/2007/15.pdf Применение генетических алгоритмов к решению задач дискретной оптимизации]. — 2007. — Нижний Новгород.
  30. 1 2 3 4 5 С. М. Авдошин, А. А. Савельева. [www.hse.ru/data/194/314/1234/%D0%90%D0%B2%D0%B4%D0%BE%D1%88%D0%B8%D0%BD.%D0%A1%D0%B0%D0%B2%D0%B5%D0%BB%D1%8C%D0%B5%D0%B2%D0%B0_%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7.pdf Криптоанализ: современное состояние и перспективы развития] (рус.). — С. 38.
  31. 1 2 Kurt M Bretthauer, Bala Shetty [www.sciencedirect.com/science/article/pii/S0377221701001795 The nonlinear knapsack problem – algorithms and applications] // European Journal of Operational Research. — 2002-05-01. — Т. 138, вып. 3. — С. 459–472. — DOI:10.1016/S0377-2217(01)00179-5.

Литература

на русском языке
  1. Ошибка Lua : attempt to index local 'entity' (a nil value).
  2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. [e-maxx.ru/bookz/files/cormen.pdf Алгоритмы: построение и анализ] = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 456-458. — ISBN 0-07-013151-1.
  3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.
  4. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. [www.mtas.ru/upload/library/atgt.pdf Прикладные задачи теории графов]. — 1-ое. — Тбилиси: ВЦ АН ГССР, 1974. — 232 с.
  5. В. Н. Бурков, Д. А. Новиков. [www.mtas.ru/start/t_garf.pdf Элементы теории графов]. — 2001. — С. 28.
  6. С. Окулов. [content.schools.by/3.orsha/library/Окулов_Программирование_в_алгоритмах.pdf Программирование в алгоритмах]. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9.
  7. Б. Шнайер. [htrd.su/wiki/_media/zhurnal/2012/03/23/todo_prikladnaja_kriptografija/cryptoshn.pdf Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си] = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  8. А. Саломаа. [tcode.tinro.ru/cryptography/src/open_key_crypt.pdf Криптография с открытым ключом] = Public-Key Cryptography. — М.: Мир, 1995. — С. 102-150. — ISBN 5–03–001991–X.
  9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6.
  10. Ошибка Lua : attempt to index local 'entity' (a nil value).
на английском языке
  1. Silvano Martelo, Paolo Toth. [www.or.deis.unibo.it/kp/Chapter1.pdf Knapsack problems]. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-2.
  2. Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack problems. — Springer-Verlag, 2003. — 548 с. — ISBN 3540402861.
  3. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür [www5.informatik.uni-erlangen.de/Forschung/Publikationen/2008/Riedhammer08-PTM.pdf Packing the Meeting Summarization Knapsack]. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.

Ссылки

  • [www.ifors.ms.unimelb.edu.au/tutorial/knapsack/index.html Welcome to the Knapsack] (англ.)
  • [www.academicearth.org/lectures/knapsack-problem-1 Knapsack Problem By Eric Grimsom John Guttag — MIT] (англ.)
  • [rosettacode.org/wiki/Knapsack_Problem Knapsack Problem solutions in many languages] (англ.)
  • [www.proggen.org/doku.php?id=algo:knapsack Das Rucksack-Problem (Knapsack Problem)] (нем.)


Отрывок, характеризующий Задача о ранце

– Я вам прямо скажу, – сказал князь Василий тоном хитрого человека, убедившегося в ненужности хитрить перед проницательностью собеседника. – Вы ведь насквозь людей видите. Анатоль не гений, но честный, добрый малый, прекрасный сын и родной.
– Ну, ну, хорошо, увидим.
Как оно всегда бывает для одиноких женщин, долго проживших без мужского общества, при появлении Анатоля все три женщины в доме князя Николая Андреевича одинаково почувствовали, что жизнь их была не жизнью до этого времени. Сила мыслить, чувствовать, наблюдать мгновенно удесятерилась во всех их, и как будто до сих пор происходившая во мраке, их жизнь вдруг осветилась новым, полным значения светом.
Княжна Марья вовсе не думала и не помнила о своем лице и прическе. Красивое, открытое лицо человека, который, может быть, будет ее мужем, поглощало всё ее внимание. Он ей казался добр, храбр, решителен, мужествен и великодушен. Она была убеждена в этом. Тысячи мечтаний о будущей семейной жизни беспрестанно возникали в ее воображении. Она отгоняла и старалась скрыть их.
«Но не слишком ли я холодна с ним? – думала княжна Марья. – Я стараюсь сдерживать себя, потому что в глубине души чувствую себя к нему уже слишком близкою; но ведь он не знает всего того, что я о нем думаю, и может вообразить себе, что он мне неприятен».
И княжна Марья старалась и не умела быть любезной с новым гостем. «La pauvre fille! Elle est diablement laide», [Бедная девушка, она дьявольски дурна собою,] думал про нее Анатоль.
M lle Bourienne, взведенная тоже приездом Анатоля на высокую степень возбуждения, думала в другом роде. Конечно, красивая молодая девушка без определенного положения в свете, без родных и друзей и даже родины не думала посвятить свою жизнь услугам князю Николаю Андреевичу, чтению ему книг и дружбе к княжне Марье. M lle Bourienne давно ждала того русского князя, который сразу сумеет оценить ее превосходство над русскими, дурными, дурно одетыми, неловкими княжнами, влюбится в нее и увезет ее; и вот этот русский князь, наконец, приехал. У m lle Bourienne была история, слышанная ею от тетки, доконченная ею самой, которую она любила повторять в своем воображении. Это была история о том, как соблазненной девушке представлялась ее бедная мать, sa pauvre mere, и упрекала ее за то, что она без брака отдалась мужчине. M lle Bourienne часто трогалась до слез, в воображении своем рассказывая ему , соблазнителю, эту историю. Теперь этот он , настоящий русский князь, явился. Он увезет ее, потом явится ma pauvre mere, и он женится на ней. Так складывалась в голове m lle Bourienne вся ее будущая история, в самое то время как она разговаривала с ним о Париже. Не расчеты руководили m lle Bourienne (она даже ни минуты не обдумывала того, что ей делать), но всё это уже давно было готово в ней и теперь только сгруппировалось около появившегося Анатоля, которому она желала и старалась, как можно больше, нравиться.
Маленькая княгиня, как старая полковая лошадь, услыхав звук трубы, бессознательно и забывая свое положение, готовилась к привычному галопу кокетства, без всякой задней мысли или борьбы, а с наивным, легкомысленным весельем.
Несмотря на то, что Анатоль в женском обществе ставил себя обыкновенно в положение человека, которому надоедала беготня за ним женщин, он чувствовал тщеславное удовольствие, видя свое влияние на этих трех женщин. Кроме того он начинал испытывать к хорошенькой и вызывающей Bourienne то страстное, зверское чувство, которое на него находило с чрезвычайной быстротой и побуждало его к самым грубым и смелым поступкам.
Общество после чаю перешло в диванную, и княжну попросили поиграть на клавикордах. Анатоль облокотился перед ней подле m lle Bourienne, и глаза его, смеясь и радуясь, смотрели на княжну Марью. Княжна Марья с мучительным и радостным волнением чувствовала на себе его взгляд. Любимая соната переносила ее в самый задушевно поэтический мир, а чувствуемый на себе взгляд придавал этому миру еще большую поэтичность. Взгляд же Анатоля, хотя и был устремлен на нее, относился не к ней, а к движениям ножки m lle Bourienne, которую он в это время трогал своею ногою под фортепиано. M lle Bourienne смотрела тоже на княжну, и в ее прекрасных глазах было тоже новое для княжны Марьи выражение испуганной радости и надежды.
«Как она меня любит! – думала княжна Марья. – Как я счастлива теперь и как могу быть счастлива с таким другом и таким мужем! Неужели мужем?» думала она, не смея взглянуть на его лицо, чувствуя всё тот же взгляд, устремленный на себя.
Ввечеру, когда после ужина стали расходиться, Анатоль поцеловал руку княжны. Она сама не знала, как у ней достало смелости, но она прямо взглянула на приблизившееся к ее близоруким глазам прекрасное лицо. После княжны он подошел к руке m lle Bourienne (это было неприлично, но он делал всё так уверенно и просто), и m lle Bourienne вспыхнула и испуганно взглянула на княжну.
«Quelle delicatesse» [Какая деликатность,] – подумала княжна. – Неужели Ame (так звали m lle Bourienne) думает, что я могу ревновать ее и не ценить ее чистую нежность и преданность ко мне. – Она подошла к m lle Bourienne и крепко ее поцеловала. Анатоль подошел к руке маленькой княгини.
– Non, non, non! Quand votre pere m'ecrira, que vous vous conduisez bien, je vous donnerai ma main a baiser. Pas avant. [Нет, нет, нет! Когда отец ваш напишет мне, что вы себя ведете хорошо, тогда я дам вам поцеловать руку. Не прежде.] – И, подняв пальчик и улыбаясь, она вышла из комнаты.


Все разошлись, и, кроме Анатоля, который заснул тотчас же, как лег на постель, никто долго не спал эту ночь.
«Неужели он мой муж, именно этот чужой, красивый, добрый мужчина; главное – добрый», думала княжна Марья, и страх, который почти никогда не приходил к ней, нашел на нее. Она боялась оглянуться; ей чудилось, что кто то стоит тут за ширмами, в темном углу. И этот кто то был он – дьявол, и он – этот мужчина с белым лбом, черными бровями и румяным ртом.
Она позвонила горничную и попросила ее лечь в ее комнате.
M lle Bourienne в этот вечер долго ходила по зимнему саду, тщетно ожидая кого то и то улыбаясь кому то, то до слез трогаясь воображаемыми словами рauvre mere, упрекающей ее за ее падение.
Маленькая княгиня ворчала на горничную за то, что постель была нехороша. Нельзя было ей лечь ни на бок, ни на грудь. Всё было тяжело и неловко. Живот ее мешал ей. Он мешал ей больше, чем когда нибудь, именно нынче, потому что присутствие Анатоля перенесло ее живее в другое время, когда этого не было и ей было всё легко и весело. Она сидела в кофточке и чепце на кресле. Катя, сонная и с спутанной косой, в третий раз перебивала и переворачивала тяжелую перину, что то приговаривая.
– Я тебе говорила, что всё буграми и ямами, – твердила маленькая княгиня, – я бы сама рада была заснуть, стало быть, я не виновата, – и голос ее задрожал, как у собирающегося плакать ребенка.
Старый князь тоже не спал. Тихон сквозь сон слышал, как он сердито шагал и фыркал носом. Старому князю казалось, что он был оскорблен за свою дочь. Оскорбление самое больное, потому что оно относилось не к нему, а к другому, к дочери, которую он любит больше себя. Он сказал себе, что он передумает всё это дело и найдет то, что справедливо и должно сделать, но вместо того он только больше раздражал себя.
«Первый встречный показался – и отец и всё забыто, и бежит кверху, причесывается и хвостом виляет, и сама на себя не похожа! Рада бросить отца! И знала, что я замечу. Фр… фр… фр… И разве я не вижу, что этот дурень смотрит только на Бурьенку (надо ее прогнать)! И как гордости настолько нет, чтобы понять это! Хоть не для себя, коли нет гордости, так для меня, по крайней мере. Надо ей показать, что этот болван об ней и не думает, а только смотрит на Bourienne. Нет у ней гордости, но я покажу ей это»…
Сказав дочери, что она заблуждается, что Анатоль намерен ухаживать за Bourienne, старый князь знал, что он раздражит самолюбие княжны Марьи, и его дело (желание не разлучаться с дочерью) будет выиграно, и потому успокоился на этом. Он кликнул Тихона и стал раздеваться.
«И чорт их принес! – думал он в то время, как Тихон накрывал ночной рубашкой его сухое, старческое тело, обросшее на груди седыми волосами. – Я их не звал. Приехали расстраивать мою жизнь. И немного ее осталось».
– К чорту! – проговорил он в то время, как голова его еще была покрыта рубашкой.
Тихон знал привычку князя иногда вслух выражать свои мысли, а потому с неизменным лицом встретил вопросительно сердитый взгляд лица, появившегося из под рубашки.
– Легли? – спросил князь.
Тихон, как и все хорошие лакеи, знал чутьем направление мыслей барина. Он угадал, что спрашивали о князе Василье с сыном.
– Изволили лечь и огонь потушили, ваше сиятельство.
– Не за чем, не за чем… – быстро проговорил князь и, всунув ноги в туфли и руки в халат, пошел к дивану, на котором он спал.
Несмотря на то, что между Анатолем и m lle Bourienne ничего не было сказано, они совершенно поняли друг друга в отношении первой части романа, до появления pauvre mere, поняли, что им нужно много сказать друг другу тайно, и потому с утра они искали случая увидаться наедине. В то время как княжна прошла в обычный час к отцу, m lle Bourienne сошлась с Анатолем в зимнем саду.
Княжна Марья подходила в этот день с особенным трепетом к двери кабинета. Ей казалось, что не только все знают, что нынче совершится решение ее судьбы, но что и знают то, что она об этом думает. Она читала это выражение в лице Тихона и в лице камердинера князя Василья, который с горячей водой встретился в коридоре и низко поклонился ей.
Старый князь в это утро был чрезвычайно ласков и старателен в своем обращении с дочерью. Это выражение старательности хорошо знала княжна Марья. Это было то выражение, которое бывало на его лице в те минуты, когда сухие руки его сжимались в кулак от досады за то, что княжна Марья не понимала арифметической задачи, и он, вставая, отходил от нее и тихим голосом повторял несколько раз одни и те же слова.
Он тотчас же приступил к делу и начал разговор, говоря «вы».
– Мне сделали пропозицию насчет вас, – сказал он, неестественно улыбаясь. – Вы, я думаю, догадались, – продолжал он, – что князь Василий приехал сюда и привез с собой своего воспитанника (почему то князь Николай Андреич называл Анатоля воспитанником) не для моих прекрасных глаз. Мне вчера сделали пропозицию насчет вас. А так как вы знаете мои правила, я отнесся к вам.
– Как мне вас понимать, mon pere? – проговорила княжна, бледнея и краснея.
– Как понимать! – сердито крикнул отец. – Князь Василий находит тебя по своему вкусу для невестки и делает тебе пропозицию за своего воспитанника. Вот как понимать. Как понимать?!… А я у тебя спрашиваю.
– Я не знаю, как вы, mon pere, – шопотом проговорила княжна.
– Я? я? что ж я то? меня то оставьте в стороне. Не я пойду замуж. Что вы? вот это желательно знать.
Княжна видела, что отец недоброжелательно смотрел на это дело, но ей в ту же минуту пришла мысль, что теперь или никогда решится судьба ее жизни. Она опустила глаза, чтобы не видеть взгляда, под влиянием которого она чувствовала, что не могла думать, а могла по привычке только повиноваться, и сказала:
– Я желаю только одного – исполнить вашу волю, – сказала она, – но ежели бы мое желание нужно было выразить…
Она не успела договорить. Князь перебил ее.
– И прекрасно, – закричал он. – Он тебя возьмет с приданным, да кстати захватит m lle Bourienne. Та будет женой, а ты…
Князь остановился. Он заметил впечатление, произведенное этими словами на дочь. Она опустила голову и собиралась плакать.
– Ну, ну, шучу, шучу, – сказал он. – Помни одно, княжна: я держусь тех правил, что девица имеет полное право выбирать. И даю тебе свободу. Помни одно: от твоего решения зависит счастье жизни твоей. Обо мне нечего говорить.
– Да я не знаю… mon pere.
– Нечего говорить! Ему велят, он не только на тебе, на ком хочешь женится; а ты свободна выбирать… Поди к себе, обдумай и через час приди ко мне и при нем скажи: да или нет. Я знаю, ты станешь молиться. Ну, пожалуй, молись. Только лучше подумай. Ступай. Да или нет, да или нет, да или нет! – кричал он еще в то время, как княжна, как в тумане, шатаясь, уже вышла из кабинета.
Судьба ее решилась и решилась счастливо. Но что отец сказал о m lle Bourienne, – этот намек был ужасен. Неправда, положим, но всё таки это было ужасно, она не могла не думать об этом. Она шла прямо перед собой через зимний сад, ничего не видя и не слыша, как вдруг знакомый шопот m lle Bourienne разбудил ее. Она подняла глаза и в двух шагах от себя увидала Анатоля, который обнимал француженку и что то шептал ей. Анатоль с страшным выражением на красивом лице оглянулся на княжну Марью и не выпустил в первую секунду талию m lle Bourienne, которая не видала ее.
«Кто тут? Зачем? Подождите!» как будто говорило лицо Анатоля. Княжна Марья молча глядела на них. Она не могла понять этого. Наконец, m lle Bourienne вскрикнула и убежала, а Анатоль с веселой улыбкой поклонился княжне Марье, как будто приглашая ее посмеяться над этим странным случаем, и, пожав плечами, прошел в дверь, ведшую на его половину.
Через час Тихон пришел звать княжну Марью. Он звал ее к князю и прибавил, что и князь Василий Сергеич там. Княжна, в то время как пришел Тихон, сидела на диване в своей комнате и держала в своих объятиях плачущую m lla Bourienne. Княжна Марья тихо гладила ее по голове. Прекрасные глаза княжны, со всем своим прежним спокойствием и лучистостью, смотрели с нежной любовью и сожалением на хорошенькое личико m lle Bourienne.
– Non, princesse, je suis perdue pour toujours dans votre coeur, [Нет, княжна, я навсегда утратила ваше расположение,] – говорила m lle Bourienne.
– Pourquoi? Je vous aime plus, que jamais, – говорила княжна Марья, – et je tacherai de faire tout ce qui est en mon pouvoir pour votre bonheur. [Почему же? Я вас люблю больше, чем когда либо, и постараюсь сделать для вашего счастия всё, что в моей власти.]
– Mais vous me meprisez, vous si pure, vous ne comprendrez jamais cet egarement de la passion. Ah, ce n'est que ma pauvre mere… [Но вы так чисты, вы презираете меня; вы никогда не поймете этого увлечения страсти. Ах, моя бедная мать…]
– Je comprends tout, [Я всё понимаю,] – отвечала княжна Марья, грустно улыбаясь. – Успокойтесь, мой друг. Я пойду к отцу, – сказала она и вышла.
Князь Василий, загнув высоко ногу, с табакеркой в руках и как бы расчувствованный донельзя, как бы сам сожалея и смеясь над своей чувствительностью, сидел с улыбкой умиления на лице, когда вошла княжна Марья. Он поспешно поднес щепоть табаку к носу.
– Ah, ma bonne, ma bonne, [Ах, милая, милая.] – сказал он, вставая и взяв ее за обе руки. Он вздохнул и прибавил: – Le sort de mon fils est en vos mains. Decidez, ma bonne, ma chere, ma douee Marieie qui j'ai toujours aimee, comme ma fille. [Судьба моего сына в ваших руках. Решите, моя милая, моя дорогая, моя кроткая Мари, которую я всегда любил, как дочь.]
Он отошел. Действительная слеза показалась на его глазах.
– Фр… фр… – фыркал князь Николай Андреич.
– Князь от имени своего воспитанника… сына, тебе делает пропозицию. Хочешь ли ты или нет быть женою князя Анатоля Курагина? Ты говори: да или нет! – закричал он, – а потом я удерживаю за собой право сказать и свое мнение. Да, мое мнение и только свое мнение, – прибавил князь Николай Андреич, обращаясь к князю Василью и отвечая на его умоляющее выражение. – Да или нет?
– Мое желание, mon pere, никогда не покидать вас, никогда не разделять своей жизни с вашей. Я не хочу выходить замуж, – сказала она решительно, взглянув своими прекрасными глазами на князя Василья и на отца.
– Вздор, глупости! Вздор, вздор, вздор! – нахмурившись, закричал князь Николай Андреич, взял дочь за руку, пригнул к себе и не поцеловал, но только пригнув свой лоб к ее лбу, дотронулся до нее и так сжал руку, которую он держал, что она поморщилась и вскрикнула.
Князь Василий встал.
– Ma chere, je vous dirai, que c'est un moment que je n'oublrai jamais, jamais; mais, ma bonne, est ce que vous ne nous donnerez pas un peu d'esperance de toucher ce coeur si bon, si genereux. Dites, que peut etre… L'avenir est si grand. Dites: peut etre. [Моя милая, я вам скажу, что эту минуту я никогда не забуду, но, моя добрейшая, дайте нам хоть малую надежду возможности тронуть это сердце, столь доброе и великодушное. Скажите: может быть… Будущность так велика. Скажите: может быть.]
– Князь, то, что я сказала, есть всё, что есть в моем сердце. Я благодарю за честь, но никогда не буду женой вашего сына.
– Ну, и кончено, мой милый. Очень рад тебя видеть, очень рад тебя видеть. Поди к себе, княжна, поди, – говорил старый князь. – Очень, очень рад тебя видеть, – повторял он, обнимая князя Василья.
«Мое призвание другое, – думала про себя княжна Марья, мое призвание – быть счастливой другим счастием, счастием любви и самопожертвования. И что бы мне это ни стоило, я сделаю счастие бедной Ame. Она так страстно его любит. Она так страстно раскаивается. Я все сделаю, чтобы устроить ее брак с ним. Ежели он не богат, я дам ей средства, я попрошу отца, я попрошу Андрея. Я так буду счастлива, когда она будет его женою. Она так несчастлива, чужая, одинокая, без помощи! И Боже мой, как страстно она любит, ежели она так могла забыть себя. Может быть, и я сделала бы то же!…» думала княжна Марья.


Долго Ростовы не имели известий о Николушке; только в середине зимы графу было передано письмо, на адресе которого он узнал руку сына. Получив письмо, граф испуганно и поспешно, стараясь не быть замеченным, на цыпочках пробежал в свой кабинет, заперся и стал читать. Анна Михайловна, узнав (как она и всё знала, что делалось в доме) о получении письма, тихим шагом вошла к графу и застала его с письмом в руках рыдающим и вместе смеющимся. Анна Михайловна, несмотря на поправившиеся дела, продолжала жить у Ростовых.
– Mon bon ami? – вопросительно грустно и с готовностью всякого участия произнесла Анна Михайловна.
Граф зарыдал еще больше. «Николушка… письмо… ранен… бы… был… ma сhere… ранен… голубчик мой… графинюшка… в офицеры произведен… слава Богу… Графинюшке как сказать?…»
Анна Михайловна подсела к нему, отерла своим платком слезы с его глаз, с письма, закапанного ими, и свои слезы, прочла письмо, успокоила графа и решила, что до обеда и до чаю она приготовит графиню, а после чаю объявит всё, коли Бог ей поможет.
Всё время обеда Анна Михайловна говорила о слухах войны, о Николушке; спросила два раза, когда получено было последнее письмо от него, хотя знала это и прежде, и заметила, что очень легко, может быть, и нынче получится письмо. Всякий раз как при этих намеках графиня начинала беспокоиться и тревожно взглядывать то на графа, то на Анну Михайловну, Анна Михайловна самым незаметным образом сводила разговор на незначительные предметы. Наташа, из всего семейства более всех одаренная способностью чувствовать оттенки интонаций, взглядов и выражений лиц, с начала обеда насторожила уши и знала, что что нибудь есть между ее отцом и Анной Михайловной и что нибудь касающееся брата, и что Анна Михайловна приготавливает. Несмотря на всю свою смелость (Наташа знала, как чувствительна была ее мать ко всему, что касалось известий о Николушке), она не решилась за обедом сделать вопроса и от беспокойства за обедом ничего не ела и вертелась на стуле, не слушая замечаний своей гувернантки. После обеда она стремглав бросилась догонять Анну Михайловну и в диванной с разбега бросилась ей на шею.
– Тетенька, голубушка, скажите, что такое?
– Ничего, мой друг.
– Нет, душенька, голубчик, милая, персик, я не отстaнy, я знаю, что вы знаете.
Анна Михайловна покачала головой.
– Voua etes une fine mouche, mon enfant, [Ты вострушка, дитя мое.] – сказала она.
– От Николеньки письмо? Наверно! – вскрикнула Наташа, прочтя утвердительный ответ в лице Анны Михайловны.
– Но ради Бога, будь осторожнее: ты знаешь, как это может поразить твою maman.
– Буду, буду, но расскажите. Не расскажете? Ну, так я сейчас пойду скажу.
Анна Михайловна в коротких словах рассказала Наташе содержание письма с условием не говорить никому.
Честное, благородное слово, – крестясь, говорила Наташа, – никому не скажу, – и тотчас же побежала к Соне.
– Николенька…ранен…письмо… – проговорила она торжественно и радостно.
– Nicolas! – только выговорила Соня, мгновенно бледнея.
Наташа, увидав впечатление, произведенное на Соню известием о ране брата, в первый раз почувствовала всю горестную сторону этого известия.
Она бросилась к Соне, обняла ее и заплакала. – Немножко ранен, но произведен в офицеры; он теперь здоров, он сам пишет, – говорила она сквозь слезы.
– Вот видно, что все вы, женщины, – плаксы, – сказал Петя, решительными большими шагами прохаживаясь по комнате. – Я так очень рад и, право, очень рад, что брат так отличился. Все вы нюни! ничего не понимаете. – Наташа улыбнулась сквозь слезы.
– Ты не читала письма? – спрашивала Соня.
– Не читала, но она сказала, что всё прошло, и что он уже офицер…
– Слава Богу, – сказала Соня, крестясь. – Но, может быть, она обманула тебя. Пойдем к maman.
Петя молча ходил по комнате.
– Кабы я был на месте Николушки, я бы еще больше этих французов убил, – сказал он, – такие они мерзкие! Я бы их побил столько, что кучу из них сделали бы, – продолжал Петя.
– Молчи, Петя, какой ты дурак!…
– Не я дурак, а дуры те, кто от пустяков плачут, – сказал Петя.
– Ты его помнишь? – после минутного молчания вдруг спросила Наташа. Соня улыбнулась: «Помню ли Nicolas?»
– Нет, Соня, ты помнишь ли его так, чтоб хорошо помнить, чтобы всё помнить, – с старательным жестом сказала Наташа, видимо, желая придать своим словам самое серьезное значение. – И я помню Николеньку, я помню, – сказала она. – А Бориса не помню. Совсем не помню…
– Как? Не помнишь Бориса? – спросила Соня с удивлением.
– Не то, что не помню, – я знаю, какой он, но не так помню, как Николеньку. Его, я закрою глаза и помню, а Бориса нет (она закрыла глаза), так, нет – ничего!
– Ах, Наташа, – сказала Соня, восторженно и серьезно глядя на свою подругу, как будто она считала ее недостойной слышать то, что она намерена была сказать, и как будто она говорила это кому то другому, с кем нельзя шутить. – Я полюбила раз твоего брата, и, что бы ни случилось с ним, со мной, я никогда не перестану любить его во всю жизнь.
Наташа удивленно, любопытными глазами смотрела на Соню и молчала. Она чувствовала, что то, что говорила Соня, была правда, что была такая любовь, про которую говорила Соня; но Наташа ничего подобного еще не испытывала. Она верила, что это могло быть, но не понимала.
– Ты напишешь ему? – спросила она.
Соня задумалась. Вопрос о том, как писать к Nicolas и нужно ли писать и как писать, был вопрос, мучивший ее. Теперь, когда он был уже офицер и раненый герой, хорошо ли было с ее стороны напомнить ему о себе и как будто о том обязательстве, которое он взял на себя в отношении ее.
– Не знаю; я думаю, коли он пишет, – и я напишу, – краснея, сказала она.
– И тебе не стыдно будет писать ему?
Соня улыбнулась.
– Нет.
– А мне стыдно будет писать Борису, я не буду писать.
– Да отчего же стыдно?Да так, я не знаю. Неловко, стыдно.
– А я знаю, отчего ей стыдно будет, – сказал Петя, обиженный первым замечанием Наташи, – оттого, что она была влюблена в этого толстого с очками (так называл Петя своего тезку, нового графа Безухого); теперь влюблена в певца этого (Петя говорил об итальянце, Наташином учителе пенья): вот ей и стыдно.
– Петя, ты глуп, – сказала Наташа.
– Не глупее тебя, матушка, – сказал девятилетний Петя, точно как будто он был старый бригадир.
Графиня была приготовлена намеками Анны Михайловны во время обеда. Уйдя к себе, она, сидя на кресле, не спускала глаз с миниатюрного портрета сына, вделанного в табакерке, и слезы навертывались ей на глаза. Анна Михайловна с письмом на цыпочках подошла к комнате графини и остановилась.
– Не входите, – сказала она старому графу, шедшему за ней, – после, – и затворила за собой дверь.
Граф приложил ухо к замку и стал слушать.
Сначала он слышал звуки равнодушных речей, потом один звук голоса Анны Михайловны, говорившей длинную речь, потом вскрик, потом молчание, потом опять оба голоса вместе говорили с радостными интонациями, и потом шаги, и Анна Михайловна отворила ему дверь. На лице Анны Михайловны было гордое выражение оператора, окончившего трудную ампутацию и вводящего публику для того, чтоб она могла оценить его искусство.
– C'est fait! [Дело сделано!] – сказала она графу, торжественным жестом указывая на графиню, которая держала в одной руке табакерку с портретом, в другой – письмо и прижимала губы то к тому, то к другому.
Увидав графа, она протянула к нему руки, обняла его лысую голову и через лысую голову опять посмотрела на письмо и портрет и опять для того, чтобы прижать их к губам, слегка оттолкнула лысую голову. Вера, Наташа, Соня и Петя вошли в комнату, и началось чтение. В письме был кратко описан поход и два сражения, в которых участвовал Николушка, производство в офицеры и сказано, что он целует руки maman и papa, прося их благословения, и целует Веру, Наташу, Петю. Кроме того он кланяется m r Шелингу, и m mе Шос и няне, и, кроме того, просит поцеловать дорогую Соню, которую он всё так же любит и о которой всё так же вспоминает. Услыхав это, Соня покраснела так, что слезы выступили ей на глаза. И, не в силах выдержать обратившиеся на нее взгляды, она побежала в залу, разбежалась, закружилась и, раздув баллоном платье свое, раскрасневшаяся и улыбающаяся, села на пол. Графиня плакала.