Укладка рюкзака. Упаковка рюкзака алгоритм


Укладка рюкзака Википедия

Пример задачи о ранце: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной

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

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

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

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

Математически задача формулируется следующим образом: имеется n{\displaystyle n} грузов. Для каждого i{\displaystyle i}-го груза определён его вес wi>0{\displaystyle w_{i}>0} и ценность vi>0{\displaystyle v_{i}>0}, i=1,2,...,n{\displaystyle i=1,2,...,n}. Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью W{\displaystyle W}. Необходимо

максимизировать ∑i=1nvixi{\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} с ограничениями ∑i=1nwixi≤W{\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} и xi∈{0,1}{\displaystyle x_{i}\in \{0,1\}} [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].

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

Одним из наиболее общих вариантов задачи о ранце является нелинейный. Его можно сформулировать следующим образом:

Пусть вектор x=(x1,..,xn)∈Rn{\displaystyle x=(x_{1},..,x_{n})\in \mathbb {R} ^{n}} определяет количество экземпляров каждого предмета в ранце. Тогда задача состоит в нахождении минимума функции

minx∈S f(x){\displaystyle \min _{x\in S}\ f(x)},

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

g(x)≤b{\displaystyle g(x)\leq b}.

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

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

  • S={0,1}n{\displaystyle S=\{0,1\}^{n}} — рюкзак 0-1
  • S=N0n{\displaystyle S=\mathbb {N_{0}} ^{n}} — неограниченный рюкзак
  • S={(x1,..,xn)∈N0n:xi≤ci}{\displaystyle S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}} — ограниченный рюкзак

Свобода в выборе функций f(x),g(x){\displaystyle f(x),g(x)} позволяет решать более широкий класс задач, включая организацию производственных мощностей (англ.)русск., оптимальное распределение семплов в районированной выборке или решение квадратичной задачи о ранце[7].

Точные методы решения

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

Дерево полного перебора, соответствующее поиску решения для трех предметов. В каждом узле определяется, будет ли данный предмет уложен в рюкзак. Цифра в узле соответствует номеру предмета. Цифры на рёбрах: 0 означает, что предмет не был взят, 1 — что был.

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

Как и для других дискретных задач, задачу о ранце можно решить, полностью перебрав все возможные решения. Допустим, имеется N{\displaystyle N} предметов, которые можно укладывать в рюкзак. Нужно определить максимальную стоимость груза, вес которого не превышает W{\displaystyle W}.

Для каждого предмета существует 2 варианта: предмет либо кладётся в рюкзак, либо нет. Тогда перебор всех возможных вариантов имеет временну́ю сложность O(2N){\displaystyle O(2^{N})}, что позволяет его использовать лишь для небольшого количества предметов[8]. С ростом числа предметов задача становится неразрешимой данным методом за приемлемое время.

На рисунке показано дерево перебора для трёх предметов. Каждый лист соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает W{\displaystyle W}[9].

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

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

Оригинальный алгоритм, предложенный Питером Колесаром (англ. Peter Kolesar) в 1967 году, предлагает отсортировать предметы по их удельной стоимости (отношению ценности к весу) и строить дерево полного перебора. Его улучшение заключается в том, что в процессе построения дерева, для каждого узла мы оцениваем верхнюю границу ценности решения, и продолжаем строить дерево только для узла с максимальной оценкой[10]. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу.

Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять только в том случае, когда удельные ценности предметов отличаются значительно[11].

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

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

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

Пусть вес каждого предмета wi{\displaystyle w_{i}} является целым неотрицательным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех w∈Z:0<=w<=W{\displaystyle w\in \mathbb {Z} :0<=w<=W}, где W{\displaystyle W} — заданная грузоподъемность. Определим m[w]{\displaystyle m[w]} как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью w{\displaystyle w}.

Для m[w]{\displaystyle m[w]} можно записать рекуррентные формулы:

  • m[0]=0{\displaystyle m[0]=0}
  • m[w]=maxwi≤w(vi+m[w−wi]){\displaystyle m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])}[12],

где vi,wi{\displaystyle v_{i},w_{i}} — ценность и вес i{\displaystyle i}-го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

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

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

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

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

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

  • m[0,w]=0{\displaystyle m[0,w]=0}
  • m[i,w]=m[i−1,w]{\displaystyle m[i,\,w]=m[i-1,\,w]}, если wi>w{\displaystyle w_{i}>w}
  • m[i,w]=max(m[i−1,w],m[i−1,w−wi]+vi){\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}, если wi≤w{\displaystyle w_{i}\leq w}

Вычисляя m[n,W]{\displaystyle m[n,W]}, можно найти точное решение. Если массив m[i,w]{\displaystyle m[i,w]} помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных[12].

1 // Ввод: 2 // Ценности предметов (загруженные в массив v) 3 // Веса предметов (загруженные в массив w) 4 // Количество предметов (n) 5 // Грузоподъемность (W) 6 7 for j from 0 to W do: 8 m[0, j] := 0 9 10 for i from 1 to n do: 11 for j from 0 to W do: 12 if w[i] > j then: 13 m[i, j] := m[i-1, j] 14 else: 15 m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси X{\displaystyle X} откладывается количество предметов, по оси Y{\displaystyle Y} — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось Y{\displaystyle Y} равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета[14].

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

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

Пусть вместимость рюкзака W=14{\displaystyle W=14}.

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

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

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

Рекуррентные соотношения можно записывать не только относительно веса предметов, но также и относительно ценности. Для этого обозначим за y[i,V]{\displaystyle y[i,V]} минимальный вес предметов, суммарной ценностью V{\displaystyle V}, который можно получить из первых i{\displaystyle i} предметов. Если необходимый вес получить невозможно, то отметим это как y[i,V]=W+1{\displaystyle y[i,V]=W+1}.

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

y[i,V]={y[i−1,V],if V<vimin{ y[i−1,V],y[i−1,V−vi]+wi},if V≥vi{\displaystyle 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}}},

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

y[0,0]=0{\displaystyle y[0,0]=0}

y[0,V]=W+1{\displaystyle y[0,V]=W+1}[15]

Приближенные методы решения

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

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

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

Время работы данного алгоритма складывается из времени сортировки и времени укладки. Сложность сортировки предметов составляет O(Nlog⁡(N)){\displaystyle O(N\log(N))}. Далее происходит вычисление того, сколько предметов поместится в рюкзак за общее время O(N){\displaystyle O(N)}[10]. Итоговая сложность O(Nlog⁡(N)){\displaystyle O(N\log(N))} при необходимости сортировки и O(N){\displaystyle O(N)} при уже отсортированных данных[10].

Пример. Пусть вместимость рюкзака W=80{\displaystyle W=80}. Предметы уже отсортированы по удельной ценности. Применим жадный алгоритм.

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

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

Следует понимать, что жадный алгоритм может привести к ответу сколь угодно далёкому от оптимального. Например, если один предмет имеет вес 1 и стоимость 2, а другой — вес W и стоимость W, то жадный алгоритм наберёт иготовую стоимость 2 при оптимальном ответе W. При этом тот же алгоритм для неограниченной задачи о рюкзаке приведёт к ответу, составляющему не менее 50% от ценности оптимального[10]. (В приведённом примере жадный алгоритм возьмёт 5 первых предметов с общей ценностью 300, и это совпадает с оптимальным решением.)

Впервые жадный алгоритм был предложен Джорджем Данцигом[16] для решения задачи о неограниченном рюкзаке.

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

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

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

  1. Найдём приближённое решение xl{\displaystyle x^{l}} при помощи жадного алгоритма. Пусть x∗{\displaystyle x^{*}} — точное решение. Тогда из оценки эффективности жадного алгоритма xl≤x∗≤2xl{\displaystyle x^{l}\leq x^{*}\leq 2x^{l}}.
  2. Отмасштабируем ценности следующим образом: vi′=⌊vizlεn⌋{\displaystyle v'_{i}=\left\lfloor {\frac {v_{i}}{\frac {z^{l}\varepsilon }{n}}}\right\rfloor }.
  3. Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение.

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

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

Пример эволюции популяции при использовании генетического алгоритма. Объектами являются строчки, кодирующие в бинарном виде какие объекты кладутся в рюкзак. Например, строчка (0,1,0,1,0) соответствует выбору коробок весами 12 кг и 7 кг .

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

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

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

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

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

Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть W{\displaystyle W} — грузоподъёмность рюкзака, wi{\displaystyle w_{i}}— вес i{\displaystyle i}-го предмета, а его стоимость vi=wi{\displaystyle v_{i}=w_{i}}. Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

W=∑i=1Nwixi, xi∈{0,1}{\displaystyle W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}}

Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор (x1,..,xn){\displaystyle (x_{1},..,x_{n})}. В качестве функции приспособленности следует использовать близость суммарного веса предметов к W{\displaystyle W}, с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем W{\displaystyle W})[19].

Определим формально функцию приспособленности f(x1,..,xn):{0,1}n→R{\displaystyle f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R} }. Пусть S{\displaystyle {\mathcal {S}}} — сумма весов всех предметов. Тогда Δmax=max(W,S−W){\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)} — максимально возможное отклонение веса предметов в рюкзаке от W{\displaystyle W}.

Пусть W′=∑i=1Nwixi{\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}} — суммарный вес предметов для данного вектора. Тогда положим:

f(x1,..,xn)={1−W−W′W,W′≤W,1−W′−WΔmax,W′>W.{\displaystyle 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}}}[19]

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

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

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

Приложения

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

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

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

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

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

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

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

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

  • Рюкзак Грэма — Шамира
  • Рюкзак Гудмана — Маколи
  • Рюкзак Наккаша — Стерна
  • Рюкзак Шора — Ривеста

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

Благодаря тому, что задачу о ранце в общем виде нельзя решить точно за приемлемое время, её можно использовать в криптографических задачах. Для этого, при публично известном наборе предметов, мы представим сообщение как набор передаваемых предметов, а отправим их суммарный вес[28].

Определение. Рюкзачным вектором A=(a1,...,an){\displaystyle A=(a_{1},...,a_{n})} назовём упорядоченный набор из n предметов, где ai{\displaystyle a_{i}} — вес i{\displaystyle i}-го предмета[30].

Рюкзачный вектор является открытым ключом. Для шифрования открытого текста его разбивают на блоки длиной n{\displaystyle n} бит, при этом каждый бит определяет наличие предмета в рюкзаке (например, открытый текст (111100){\displaystyle (111100)} соответствует наличию первых четырёх из шести возможных предметов в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие[28].

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

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

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

Открытый текст 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

Примечания

  1. ↑ Silvano, 1990, p. 1.
  2. ↑ 1 2 3 Silvano, 1990, p. 2.
  3. ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004, p. 127.
  4. ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004, p. 147.
  5. ↑ Silvano, 1990, p. 157.
  6. ↑ G. Gallo, P. L. Hammer, B. Simeone Quadratic knapsack problems (англ.) // Mathematical Programming Studies. — 2009. — 24 февраль (vol. 12). — P. 132-149. — ISSN 0303-3929.
  7. ↑ 1 2 Bretthauer, Shetty, 2002.
  8. ↑ Окулов, 2007, pp. 92-93.
  9. ↑ Окулов, 2007, pp. 101-105.
  10. ↑ 1 2 3 4 5 Martello S., Toth P. Knapsack problems: algorithms and computer implementations. — John Wiley & Sons Ltd., 1990. — С. 29,50. — 296 с. — ISBN 0-471-92420-2.
  11. ↑ Бурков, Горгидзе, Ловецкий, 1974, с. 225.
  12. ↑ 1 2 3 Романовский И.В. Алгоритмы решения экстремальных задач. — Наука, 1977. — С. 252-259. — 352 с.
  13. ↑ Стивен С. Скиена. Алгоритмы. Руководство по разработке. — 2-e. — СПб: БХВ-Петербург, 2011. — С. 448-451. — 720 с. — ISBN 978-5-9775-0560-4.
  14. ↑ 1 2 Новиков, 2001, с. 12.
  15. ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004.
  16. ↑ Dantzig G. B. Discrete-Variable Extremum Problems // Oper. Res. — Institute for Operations Research and the Management Sciences, 1957. — Vol. 5, Iss. 2. — P. 266–277. — ISSN 0030-364X; 1526-5463 — doi:10.1287/OPRE.5.2.266
  17. ↑ Ariel Kulik, Hadas Shachnai 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.
  18. ↑ Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. Применение генетических алгоритмов к решению задач дискретной оптимизации. — 2007. — Нижний Новгород.
  19. ↑ 1 2 3 4 5 С. М. Авдошин, А. А. Савельева. Криптоанализ: современное состояние и перспективы развития (рус.). — С. 38.
  20. ↑ G. B. Mathews On the partition of numbers (англ.). — 1897. — P. 486-490.
  21. ↑ Kellerer, Pferschy, Pisinger, 2004, p. 3.
  22. ↑ Kellerer, Pferschy, Pisinger, 2004, p. 9.
  23. ↑ Р. Карп Reducibility Among Combinatorial Problems (англ.). — 1972.
  24. ↑ Riedhammer et al, 2008, pp. 2436.
  25. ↑ Шнаер, 2002, p. 19.2.
  26. ↑ Габидулин, Кшевецкий, Колыбельников, 2011.
  27. ↑ Бурков, Горгидзе, Ловецкий, 1974, p. 217.
  28. ↑ 1 2 3 4 Шнаер, 2002, p. 19.1.
  29. ↑ Kin Ming Lai. Knapsack Cryptosystems: The Past and the Future (рус.). — 2001.
  30. ↑ Саломаа, 1995, p. 103.

Литература

на русском языке
  1. Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 160–163. — 576 с. — ISBN 978-5-8459-0987-9
  2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = 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. Бурков В. Н., Горгидзе И. А., Ловецкий С. Е. Прикладные задачи теории графов / под ред. А. Я. Горгидзе — Тбилиси: Вычислительный центр АН СССР, 1974. — 231 с.
  5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
  6. С. Окулов. Программирование в алгоритмах. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9.
  7. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — М.: Мир, 1995. — С. 102-150. — ISBN 5–03–001991–X.
  9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6.
  10. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
  11. Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 2. — С. 209-212.
на английском языке
  1. Silvano Martelo, Paolo Toth. Knapsack problems. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-2.
  2. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems — Springer Science+Business Media, 2004. — 548 p. — ISBN 978-3-642-07311-3 — doi:10.1007/978-3-540-24777-7
  3. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür Packing the Meeting Summarization Knapsack. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
  4. Bretthauer K. M., Shetty B. The nonlinear knapsack problem – algorithms and applications // European Journal of Operational Research — Elsevier, 2002. — Vol. 138, Iss. 3. — P. 459–472. — ISSN 0377-2217; 1872-6860 — doi:10.1016/S0377-2217(01)00179-5

Ссылки

wikiredia.ru

Задача упаковки рюкзака

Задача упаковки рюкзака: Как подобрать коробки так, чтобы их стоимость была максимальной, а суммарный вес не более 15 кг?

Задача упаковки рюкзака ( англ. Knapsack problem ) - Задача комбинаторной оптимизации. Задача состоит в наполнены рюкзака, который способен выдержать некоторую максимальную массу, предметами, каждый из которых имеет стоимость (или полезность) и массу. Необходимо выбрать объекты таким образом, чтобы максимизировать суммарную стоимость (или пользу), но не превысить максимально допустимую массу.

1. История

1.1. Исследования

Задача упаковки рюкзака является одной из 21 NP-полных задач Ричарда Карпа ( англ. Richard Karp ) Изложенных в его статье 1972 года. Интенсивное исследование проблемы началось с середины ХХ века но известное упоминание еще ​​в 1897 году, в статье Джорджа Мэтьюза Балларда [1]. Описание задачи достаточно простое, но решение - сложное. Существующие алгоритмы, на практике, способны решить задачи достаточно больших размеров. Однако, уникальная структура задачи, а также тот факт, что она присутствует как подзадача в больших, общих проблемах, делает ее важной для научных исследований.

2. Применение

Задача упаковки рюкзака используется для моделирования различных проблем, в частности:

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

Также исследование этой задачи полезно для поиска решений методом генерирования столбцов и в задаче загрузки контейнеров.

Задача происходит от ситуации, когда путешественник оказывается перед выбором предметов, необходимо взять в путешествие: следует выбрать самое, но не перегрузить рюкзак.

3. Постановка задачи

Задачу упаковки рюкзака можно определить средствами математического аппарата. Пусть каждому объекту для упаковки сопоставлены индекс i, который принимает значения от 1 до n. Числа и соответствуют весу и стоимости объекта i. Максимальная допустимая масса, которую способен выдержать рюкзак, равна W.

0-1 задача упаковки рюкзака

Существует много вариантов заполнения рюкзака. Для описания отдельного варианта упаковки необходимо указать для каждого объекта, избран (упаковано). Для этого можно использовать двоичный вектор , Компонента которого равен 1, если i-тый объект запаковано, и 0 если нет. Этот вектор называется вектором заполнения. Вес и стоимость упакованных предметов, можно вычислить как функцию от вектора заполнения.

Для заданного вектора заполнения X стоимость предметов упакованных в рюкзак равна:

Аналогично, общая масса предметов равна:

Таким образом, задача упаковки рюкзака заключается в отыскании такого вектора заполнения , Которая максимизирует функцию при условии:

(1)

То есть, общая масса выбранных предметов не превышает возможности рюкзака .

Вообще, действуют следующие дополнительные условия:

  • : Все доступные объекты невозможно положить в рюкзак вместе;
  • : Любой дополнительный объект предпочитает;
  • : Любой объект использует ресурсы.

Терминология:

  • Функция - Называется целевой;
  • Любой вектор , Что соответствует условию (1), называется допустимым;
  • Если стоимость максимальная, то вектор называется оптимальным.

Предположим, кроме стоимости предметы имеют еще одну характеристику (например, плотность). Задача поиска вектора заполнения , Который максимизирует обе функции (суммарная стоимость и суммарная плотность) является многокритериальным вариантом 0-1 задачи упаковки рюкзака. [2]

Ограниченная задача упаковки рюкзака ограничивает количество копий каждого вида предмета максимальным целым значением . Математически эту задачу можно сформулировать так:

  • максимизировать
  • при

Неограниченное задача упаковки ранца (НЗПР) не накладывает верхнего предела для количества копий каждого вида предмета.

Особый интерес представляет частный случай задачи упаковки рюкзака с такими свойствами:

  • она является проблемой выбора,
  • она является 0-1 задачей,
  • для каждого вида предмета вес равен стоимости: .

В этом случае задача эквивалентна такой задачи: задано множество неотрицательных целых чисел, существует любая ее подмножество, сумма элементов которой составляет точно W? Или, если допускается отрицательная вес и W равна нулю, то задачей является: задано множество целых чисел, существует непустое подмножество, сумма элементов которой точно равна 0? Этот частный случай называется задачей суммы подмножества. В области криптографии термин задача упаковки рюкзака часто используется для обозначения конкретно задачи суммы подмножества.

Если допускается несколько рюкзаков, то задачу лучше рассматривать как задачу упаковки в контейнеры.

3.1. Формулировка средствами теории множеств

Задачу упаковки рюкзака можно описать средствами теории множеств. [3]

Пусть заданы множество объектов , Вес , И стоимость для каждого объекта и максимальную допустимый вес . Необходимо найти подмножество , Такую, чтобы:

и .

4. NP-сложность

В контексте исследования алгоритмической сложности задачи, ее оптимизационное формулировки меняют на задачу распознавания. Представление в виде задачи распознавания вводит дополнительный параметр P - желаемая стоимость предметов в рюкзаке и ставит вопрос, существует еще один вариант упаковки, с суммарной стоимостью упакованных предметов больше P. [ 3] Цель введения задачи распознавания состоит в том, что с точки зрения теории вычислительной сложности и NP-полноты для нее легче определять сложность. Если целевую функцию не сложно вычислять, то задача распознавания не сложнее соответствующую задачу оптимизации. Таким образом, с NP-полноты задачи распознавания следует NP-полнота задачи оптимизации. [4] [3]

Задача распознавания для оптимизационной задачи 0-1 упаковки рюкзака формулируется так: Задан конечное множество U объектов, вес , Стоимость для каждого объекта и целые числа W (емкость рюкзака) и P (желательно стоимость). Существует такая подмножество , Что:

, И ?

5. Приближенные методы решения

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

Далее под эффективностью предмета понимается отношение его стоимости к весу. Чем выше эффективность предмета, тем полезнее он для упаковки.

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

Две фазы жадного алгоритма: Слева: благоустройство предметов за их эффективностью (в этом случае стоимость на кило веса). Справа: упаковка в рюкзак, если есть возможность. Полученный решение дает $ 11 и 11 кг, в то время как оптимальный $ 12 и 14 кг.

Одним из простейших алгоритмов поиска приблизительного решения является жадный алгоритм. Идея алгоритма заключается в том, чтобы класть в рюкзак в первую очередь эффективные предметы, вплоть до его заполнения:

упорядочить предметы в убывающем порядке эффективности w_пак: = 0 для i от 1 до n если w [i] + w_пак тогда x [i]: = 1 w_пак: = w_пак + w [i] иначе x [i] = 0 конец если конец для

6. Точные методы

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

6.1. Динамическое программирование

Задача упаковки рюкзака имеет свойство суб-оптимальной структуры, т.е. существует возможность найти оптимальное решение задачи по i переменными на основе решения задачи по i-1 переменными. Это свойство позволяет применение средств динамического программирования для решения задачи упаковки рюкзака.

Пусть требуется решить 0-1 задачу упаковки рюкзака. Обозначим через KP (i, c) максимальную стоимость первых i предметов с общим весом меньше или равной c. Надо найти KP (n, W).

Идея состоит в том, что оптимальное решение задачи KP (i, c) можно получить, используя решения двух простых задач:

  • задачи с i-1 переменными для рюкзака с такой же емкостью c (KP (i-1, c)), и ;
  • задачи с i-1 переменными для рюкзака с емкостью ( ) И .

Решение задачи упаковки рюкзака с 0 переменными (KP (0, *)) равна нулю. Решение задачи упаковки рюкзака при c = 0 (KP (*, 0)) также равен нулю.

Теперь можно записать рекурсивно:

Затем строится таблица T [i, c], элементы которой содержат значения решений задач KP (i, c) в следующий способ:

для c от 0 до W делать T [0, c] = 0 конец для для i от 1 до n делать для c от 0 до W делать если c> = w [i] то T [i, c] = max (T [i-1, c], T [i-1, cw [ i]] + p [i]) иначе T [i, c] = T [i-1, c] конец если конец для конец для вывести T [n, W]

Когда таблица построена, случай задачи T [n, W] следует свести к случаю T [0, *].

Временная сложность этого алгоритма равна . Алгоритм имеет два преимущества:

  1. Скорость;
  2. Не требуется сортировка переменных.

и недостаток:

  1. требует сравнительно много памяти (что делает его неприемлемым для решения больших задач).

Этот метод был разработан Робертом Гарфинкель и Джорджем Немгаузером в 1972 году. [5]

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

Подобно другим задач комбинаторной оптимизации, задача упаковки рюкзака может быть решена методом ветвей и границ ( англ. Branch-and-bound algorithm ). Применение метода ветвей и границ к решению задачи упаковки рюкзака впервые предложил Колесар в 1967 году. Вариант алгоритма разработан Гринбергом и Хегеричем в 1970 году имел существенно более низкие требования к памяти и времени. Горовиц и Сане в 1974 году предложили свой алгоритм построен на основе предыдущих вариантов. Этот алгоритм эффективный и самый простой для реализации по сравнению с предыдущими алгоритмами. Предложенный Мартэло и тозом алгоритм [6] широко распространен. Преимуществом этого метода являются низкие требования к объему требуемой памяти.

См.. также

Примечания

  1. (Англ.) GB Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897.
  2. Matthias Ehrgott Multicriteria Optimization. - Springer, 2005. ISBN 3-540-21398-8.
  3. ↑ а б в (Англ.) Michail G. Lagoudakis, The 0-1 Knapsack Problem - An Introductory Survey - www2.isye.gatech.edu / ~ mlagouda / acadpape.html, 1996.
  4. Garey MR, Johnson DS, Computers and Intractability: A Guide to the Theory of NP-completeness, WH Freeman and Comp., San Francisco, 1979.
  5. (Англ.) RS Garfinkel et GL Nemhauser. Integer Pogramming. John Wiley & Sons, New York, 1972. ISBN 0-471-29195-1.
  6. (Англ.) Silvano Martello et Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 ISBN 0471924202.
  • (Англ.) Hans Kellerer, Ulright Pferschy and David Pisinger, Knapsack Problems, Springer, 2004 ISBN 3-540-40286-1.
  • (Англ.) Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., Pp. 163-166, 1985.

www.nado.znate.ru

Упаковка рюкзака методом динамического программирования - Лямбда

Упаковка рюкзака методом динамического программирования [Jan. 30th, 2006|11:49 am]

Лямбда - функциональное программирование

(Вдогонку к одному из предыдущих постов) -- Упаковка рюкзака методом динамического программирования -- -- Пусть `bestKnap' x - это максимальный (для данного набора предметов) -- рюкзак размером не больше x. precomputeKnapsFor items = -- Рассчитав значения bestKnap для всех возможных размеров рюкзака -- мы сможем легко и просто решить задачу упаковки любого рюкзака :) let precomp = map bestKnap [0..] -- Как же посчитать bestKnap? Для рюкзака размером 0 максимальный -- размер рюкзака, очевидно, равен 0: bestKnap 0 = (0, []) -- Для лимита, большего нуля, максимальный рюкзак вычисляется так: bestKnap limit = -- 1. Берем предметы, которые могут влезть в такой рюкзак (smallEnough): let smallEnough = filter (<=limit) items in -- 2. Пусть вес одного из таких предметов равен 'x'. Добавим -- его к максимальному рюкзаку, вес которого <= (limit-x) case [ (x + size, x:ls) | x <- smallEnough , x>0 , let (size,ls)=precomp!!(limit-x) , not (x `elem` ls) ] of [] -> (0,[]) -- 3. Выберем наилучший результат среди всех предметов из smallEnough knaps -> maximumBy cmpSize knaps cmpSize a b = compare (fst a) (fst b) in precomp -- Рассчитав таким образом решение задачи упаковки рюкзака для всех его возможных размеров, -- нам остается только взять решение для требуемого размера :) knap'' limit items = (precomputeKnapsFor items)!!limit
Comments:

Замечательная программка, только не работает, если есть одинаковые предметы. Внимание, контрольный вопрос: как это поправить, не убивая эффективности программы?

Э-э-э... убрать проверку на одинаковость? not (x `elem` ls)?

Это я сказал не подумав. Сейчас подумаю.

occurancesOf x ls < occurancesOf x smallEnough? Но это убьет эффективность.

Здесь bestKnap и, соответственно, precomp должны иметь переменную items не как свободную, а как связанную, чтобы можно было передавать ее как delete x items. Но тогда из-за копирований списка эффективность снизится.

From: _adept_2006-01-30 12:56 pm (UTC)

Ну, давайте их понумеруем ...

(Link)

... и сравнивать будем с учетом номера. А перед получением окончательного результата эту нумерацию выкинем. -- Упаковка рюкзака методом динамического программирования -- -- Пусть `bestKnap' x - это максимальный (для данного набора предметов) -- рюкзак размером не больше x. precomputeKnapsFor items = -- Рассчитав значения bestKnap для всех возможных размеров рюкзака -- мы сможем легко и просто решить задачу упаковки любого рюкзака :) let precomp = map bestKnap [0..] -- Как же посчитать bestKnap? Для рюкзака размером 0 максимальный -- размер рюкзака, очевидно, равен 0: bestKnap 0 = (0, []) -- Для лимита, большего нуля, максимальный рюкзак вычисляется так: bestKnap limit = -- 1. Берем предметы, которые могут влезть в такой рюкзак. -- Пусть вес одного из таких предметов равен 'x'. Добавим -- его к максимальному рюкзаку, вес которого <= (limit-x) case [ (size x + s, x:ls) | x <- filter ((inRange 1 limit).size) items , size x > 0 , let (s,ls)=precomp!!(limit - size x) , x `notElem` ls ] of [] -> (0,[]) -- 3. Выберем наилучший результат среди всех предметов из smallEnough knaps -> maximumBy cmpSize knaps cmpSize a b = compare (fst a) (fst b) size (_,s) = s inRange low high x = x >= low && x <= high in precomp -- Рассчитав таким образом решение задачи упаковки рюкзака для всех его возможных размеров, -- нам остается только взять решение для требуемого размера :) knap'' limit items = let (s, numbered_items) = (precomputeKnapsFor (zip [0..] items))!!limit in (s, map snd numbered_items)
From: lomeo2006-01-30 01:04 pm (UTC)

Re: Ну, давайте их понумеруем ...

(Link)

Класс! Я же думал попробовать zip [1..] для items, но до конца не додумал :-(P.S. Маленькое замечание: inRange :: (Ix a) => (a,a) -> a -> Bool уже есть в пакете Ix.

From: ex_ex_zhuzh3006-01-30 02:10 pm (UTC)

Re: Ну, давайте их понумеруем ...

(Link)

Я сделал так:

было ", not (x `elem` ls)"стало ", length (filter (==x) ls) < length (filter (==x) items)"

Правильно?

From: _adept_2006-01-30 08:13 pm (UTC)

Re: Ну, давайте их понумеруем ...

(Link)

Правильно-то оно правильно, но вот насколько оно будет эффективно?

From: ex_ex_zhuzh3006-01-30 10:30 pm (UTC)

Re: Ну, давайте их понумеруем ...

(Link)

Пронумеровать, может быть, и эффективнее, но вроде бы ненамного (в константу раз). elem проходит в среднем половину списка.

Я чё-то не понимаю, причём тут динамическое программирование, причём тут эффективность? Программа перебирает решения для всех размеров от 1 до заданного, так что ли? А если в рюкзак кладутся автомобили, вес которых указан в миллиграммах, что тогда?

From: _adept_2006-01-30 02:02 pm (UTC)

А тогда ..

(Link)

.. надо применять другой метод, только и всего :)

Метод динамического программирования тут при том, что он эффективен при малых размерах рюкзка, и, следовательно вполне себе имеет практическое применение. Сложность у него будет O(nC), где n - кол-во предметов, а C - размер рюкзака. Таким образом, он позовляет решать задачу упаковки рюкзака за псевдо-полиномиальное время, при том что задача - NP-полная.

перебирает решения для всех размеров от 1 до заданного

Не для всех, совсем не для всех ;) В это нужно вникнуть, да.

Я так понимаю, только для возможно полезных.

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

Что поделать, на то задача и NP-полная.

> let smallEnough = filter (<=limit) items in > case [ (x + size, x:ls) | x <- smallEnough> , x>0> , let (size,ls)=precomp!!(limit-x)> , not (x `elem` ls) Я бы это чуть чуть сократил какcase [ (x + size, x:ls) | x <- filter (inRange (1,limit)) items, let (size,ls) = precomp!!(limit-x), x `notElem` ls

А! Еще одно прикольное наблюдение: одному моему другу легче (гораздо!) читать where, чем let..in. Почему - не знаю.

> одному моему другу легче (гораздо!) читать where, чем let..in.

Мне, кстати, тоже (особенно если названия локальных переменных достаточно читабельны)

let..in и where как программирование снизу вверх и сверху вниз :-)Может в это все дело?

Оригинальная гипотеза :). Кстати, в моем случае - даже в чем-то верная.

ru-lambda.livejournal.com


Смотрите также