Динамическое программирование: рюкзак, НОП, расстояние Левенштейна, порядок перемножения матриц — авторское изложение

ru · official · sha256:95088a47850bd0ddeb06c045f557b64e717aa558ca645ebe7f2fc0e32c5afc37

§1. Подзадача, оптимальная подструктура и порядок заполнения Динамическое программирование применимо, когда задача обладает ОПТИМАЛЬНОЙ ПОДСТРУКТУРОЙ: оптимальное решение содержит оптимальные решения подзадач. Второе условие — ПЕРЕСЕЧЕНИЕ подзадач: одна и та же подзадача встречается многократно. Без первого условия метод неверен, без второго — не выгоден, и различать эти два случая обязательно. Состояние — параметры подзадачи. Значение — оптимум по этой подзадаче. Рекуррентное соотношение выражает значение состояния через значения меньших состояний. База — состояния, значения которых заданы прямо. Порядок заполнения таблицы обязан быть таким, чтобы всякое состояние вычислялось после всех состояний, от которых оно зависит. Порядок есть часть описания, а не деталь реализации: неверный порядок читает незаполненные ячейки и даёт неверный результат молча. Заполнение снизу вверх и запоминание сверху вниз — два устройства одного метода. Первое обходит все состояния, второе — только достижимые; изложение всюду фиксирует заполнение снизу вверх и говорит об этом. Восстановление решения — отдельный шаг, а не побочный результат заполнения. Оно ведётся обратным проходом по таблице либо по сохранённым решениям. Описание, выдающее только ЗНАЧЕНИЕ оптимума, задачи «предъявить решение» не решает, и смешивать эти две задачи нельзя. Сокращение памяти до одной строки таблицы возможно там, где состояние зависит только от предыдущей строки. Оно делает восстановление решения невозможным без дополнительных ухищрений — это цена, и она называется вместе с выигрышем.

Ссылаются нормы: AnswersHere, f-0863235ca6d0ca5f124b47d4, f-0b1982327b39ec2ce87abeb9, f-100e26cf5f19742ecf3fe348, f-242f222a5a44403badc586e8, f-2e0f4a96fb4d705f7961af85, f-331d103ec360ee5d7ea6edad, f-34a49d8cdebe8f84d97035bf, f-35c285c1afbd187d3a9c4472, f-40fe36d44c14e4460da1bbee, f-40fea3d2eea5762f45238840, f-4198178638f30a5d6c0b24c6, f-44a20da7d0184c1f67d161f2, f-57aa14b7df9bb45aa6e575d5, f-5d7a1307c97c6cc4cd3bf50e, f-69f86138460b704821842bd8, f-729f2530fab1eac361bc2bab, f-83fe4a7c242ee86cc7c13144, f-9c6c3ec5489b221a69fc0b40, f-9dc4e708ecf7e6ef04b3e8be, f-ae709ebe60a139932d4e7f56, f-af680dc581099ddff5389497, f-ce6eb18f5f90f83d99559cc0, f-cff68d8bd934e1f5e13ea6f4, f-d6b46bcd95bc84ebaa153a25, f-de1aa4ae67120347e74d08b4, f-e52c557942b060aea732e336, f-e66261c9af1e84829eb8571e, f-e851da5fe92640822e3dec14, f-e8937b6aa814140071b1be18, f-f3a5fe571f830776a730bed0, f-f5440cef9b342b1f22d618b5, f-fdecfe395e97babe04cb1386

ru · official · sha256:f2752d42553c6c72c24bc0aade9ac8a7a6b8fd77f7c9652471cc4868b2ec8da8

§2. Рюкзак 0/1 Задача: по набору из n предметов с целыми весами и произвольными ценностями и по целой вместимости W выбрать подмножество наибольшей суммарной ценности с суммарным весом не более W. Каждый предмет берётся не более одного раза — в этом смысл обозначения 0/1. Вариант — таблица по двум параметрам: числу рассмотренных предметов и оставшейся вместимости. Значение состояния есть наибольшая ценность, достижимая первыми i предметами при вместимости w. Рекуррентное соотношение: предмет либо не берётся, и значение равно значению при i − 1 и той же вместимости, либо берётся, если его вес не превосходит w, и значение равно сумме его ценности и значения при i − 1 и вместимости w минус его вес. Берётся большее из двух. Условие «вес не превосходит w» обязано проверяться ДО обращения к таблице: без него читается ячейка с отрицательным индексом. Целочисленность весов существенна: таблица индексируется вместимостью, и при вещественных весах состояний становится бесконечно много. Это ПРЕДУСЛОВИЕ, а не удобство. Оценка: время и память порядка произведения n на W. Это ПСЕВДОПОЛИНОМИАЛЬНАЯ оценка: она полиномиальна по значению W, но экспоненциальна по длине его записи. Задача о рюкзаке NP-трудна, и настоящая оценка ей не противоречит — обстоятельство, которое обязано называться, иначе описание выглядит опровержением известного результата. Восстановление набора предметов ведётся обратным проходом: если значение при i отличается от значения при i − 1, предмет i взят.

Ссылаются нормы: f-0364e33d2f84c84af2ff3fd1, f-0586a317f18469a3bb0bbfdd, f-06532b1eda6af18ebed10592, f-07e39df2f4d6ca02705fe4d2, f-08a59a6ebc19bd975cfa93df, f-08dbaa533d70b5cbec1c9e9c, f-09177623e4c857d2d3de99f0, f-0bacce046b4a326c57face58, f-0c2dc06bbb65bb34d85080a5, f-0c446e40306d35f6720d1248, f-133b4cb296b41d8a5558a810, f-17bed850e9e7bb6a57e03491, f-1b8c0bb02ecab6fa72e8542e, f-20df73f6231ab8aa2a335b3e, f-2495e921d102db28fd09cf62, f-2574f46486e5829681236212, f-26e623a14483e227acecce5f, f-27c4edba2610db66906c50b0, f-2acfe40ca5e2da45605e7c8e, f-2ae610e5e9f5aa01eda24a7c, f-2fa7d558fc6a738d80da3384, f-319277ee2108e8a7af8029e5, f-36cd9551c484f95b199b8848, f-3e1c91b7d2ff8d4a77bbf916, f-3e740eead5d1f9df7d0aca8c, f-3f7623c3a46104a1602fab62, f-43cbf2dea85ff8e2395a7f2d, f-478407fb477f1963433f70d8, f-47e7ed64b907a9c2aa3c782e, f-486bd4685f0b45ac93f76ec9, f-5065fe8181a69f6da41e8275, f-51783c3cbefbc6c3f85736b5, f-53e273da3e2e8ff9b0d3a809, f-5a428f0f4dd68a10711a0033, f-5ca46ffba52f540d1f60932d, f-5cef53fa5f416253903b0760, f-5ec622c7bbb0e4608deb4baa, f-611d303a7beb00862fbdeb02, f-68f355263a8129962a6a113f, f-6ce9c48b8da8114d3ce901cf, f-6dfb0492d485923414296bf1, f-6f80226925dfaac4347a8a99, f-6fe9c8e06c1f579de95c1c56, f-724db5d12d62359f903cbed6, f-742d8e19d37482dd4b7d2b73, f-75a9897b5346b1f8674cf15a, f-76a1076659a61844cd934aa3, f-77ae57d080bfe43b7771480e, f-79516a61fa43f78863304083, f-80d3a7145c09c741afec9586, f-81ac2d70ab391ecc8113c0ab, f-836bbd3f96f5f87ee53d330e, f-84c7c8c1287df19478d0a92a, f-9311873f524b253919136095, f-93a1ac235240bf803296a3c4, f-94558e93b6f545875f04367e, f-97b72f9ba153dff6d6497d14, f-983f00f4cad47f022e0df145, f-9ae490ca82c4464b60128bc4, f-9ed0d193adfdbc1745882712, f-a442cbed8e5377dcadd010d1, f-a46bc45e9fc49537dfb836df, f-a5c770e0288c1306ff40d806, f-a963d1836b62d26146563c2f, f-adb5c47fe833456418a492dc, f-ae4d4af6817da031ef3dc6d1, f-b38988b804ae6f51fe46323d, f-b3fda17df3082705e788c841, f-b424fda4ac625ec80ea96c81, f-b5d3e730bf3b8eebb43ea25a, f-b620385a4b59ef974a7a8c44, f-b7864dd9484e2ead5f1c6a03, f-bd49a1448e1bf7fddbd231f8, f-be42e0dbb9f6219d65209f76, f-bfaa5c916672fd460b5758a2, f-c2e5d2e578ad08ebd01dc9b8, f-c4839cdfda0acbb76c662da9, f-c64bde95b4930f2f71dc1fdd, f-c6e1e29f91aea529f0f608b9, f-c9e069da3d8cbae26cb0ee41, f-ca46cd5d0b408f0e7af65035, f-cc6e6f3d9db5f8a776141df8, f-d3dad7b0543760d2e367960d, f-d4c85f301d3ca76c691ed2e4, f-d4c9ac3af86fd07c92e9ea98, f-dcb23ab92e99f4bcf32d904e, f-df7784cebd7d6ed06a4cd82b, f-dfce4eb10f24e1b52e4902ec, f-e2a6246aee0548a580f1894e, f-e73c47e31d5d0359bf0c4984, f-e7c39ff4f5db97c36725c3bc, f-e9813c5f3989453a72309f0a, f-eac9cb0626eb290f06762b18, f-ed0f7239718e0008aae9452d, f-ee74db13da61f402be983370, f-ef1274f67b58a03f9d9d41d6, f-f2f2aa16d36d198c687c7df6, f-f993ad83abcc302585e8f0ef, f-ffaaea270e0f80d12491aff3

ru · official · sha256:f0ab4c9ddf9db1953fe6e51ed1d82bf332c3cc239e28dc6fad08e856d7546d87

§3. Наибольшая общая подпоследовательность Задача: по двум последовательностям найти наибольшую по длине последовательность, являющуюся подпоследовательностью обеих. Подпоследовательность получается вычёркиванием элементов без перестановки оставшихся; непрерывности не требуется, и смешение с подстрокой — частая ошибка. Вариант — таблица по длинам рассмотренных префиксов. Значение состояния есть длина наибольшей общей подпоследовательности первых i элементов первой последовательности и первых j элементов второй. Рекуррентное соотношение: при совпадении элементов значение равно значению при (i − 1, j − 1), увеличенному на единицу; при несовпадении — большему из значений при (i − 1, j) и (i, j − 1). База: нулевая длина при пустом префиксе любой из последовательностей. Основание первого случая: если последние элементы совпадают, существует наибольшая общая подпоследовательность, оканчивающаяся этим элементом. Утверждение неочевидное и доказывается обменным доводом; доказательство остаётся в источнике. Восстановление самой подпоследовательности ведётся обратным проходом от правого нижнего угла; при равенстве значений выбор направления произволен, и разные выборы дают разные, но равные по длине ответы. Единственности решения нет, и это надо называть. Оценка: время и память порядка произведения длин. Сокращение памяти до одной строки возможно для ДЛИНЫ, но делает восстановление невозможным без дополнительных приёмов.

Ссылаются нормы: f-0040d5c4852aa45741ad9e9d, f-02d377896afe047b8aacc826, f-05586121d5e9ac7a5e2bb7a3, f-06bd3e2e5389b4a63d320700, f-0a0139a3be821a15d5d1b0bd, f-105fe09933601f4788dd1017, f-160be898e995c7e0291896f7, f-197b8b2b4c1e4697f68af7c4, f-1b2388ef73e41ec9dd99e12b, f-1b80b0f53d28c5902f95f4c7, f-1ed552ba7a62af942b64d61e, f-1f018aa6c6718c24464f59f5, f-217c73ee7cb611ff2f516d62, f-21cf084e67c02687b9f06109, f-2287eefb75f234115786fc0f, f-260f740257c5be8208f8347c, f-26d9423dd4d2b421261b4ca4, f-27710e65b73b73a378bbfd09, f-360d6786c62a9b46074f6424, f-3a15a779f82494caf707e290, f-3ae7a6113145b1c23f11c3f9, f-3c912a24cb034408cebbdabc, f-40a7dada3d4f24731a71d51d, f-46adfc556563282a1ed85dac, f-4d7f3b5082fc86ebea1f4571, f-4e5aeec73efee3cd37a88148, f-5390d7bbfef9886bca9848e7, f-56b7189eb43acf6a4600b302, f-5998377d5139a075c844069d, f-60e749640864ebca73706635, f-6346e9ed6d9467c8ca4bb718, f-656dc706c2b77441b2914ba4, f-66a230c391a77d53501039d1, f-66a64d6597f5ec5a9fe1f5db, f-67d617c1c0f549d0e347ce7c, f-6a01d357929c063b18d6e1d1, f-6f0fcad5437873f472eb1d0d, f-708029e18bc4b9e4732d6330, f-743c5187c31b7dd65dca4808, f-7f75b3a963212a72691fd2f2, f-828bdab989c3af64b312ec3a, f-87acd5f3d5b4043508f18196, f-88205133c58da5e57c2292cd, f-8feeb9ba1537f7c26e225e6c, f-96f0c75d0d07d1e375c3ed05, f-997ded0e6184d2c3e6659929, f-9c3fb03bf372669a01406553, f-9cb38ec696cd2b1d41a8e065, f-9cc713aa6f9e58c9e0593b0d, f-9f34b961a08ee49395749b60, f-9f6216d9605e25f51f6de7f6, f-a1696f19c079c830e345b8eb, f-a250b06a7069989c0b3adeff, f-a41584d5088064f87bce0c3a, f-a6e8a804e7ce91b8701e4762, f-a7929846067402a3261293a9, f-abb5f75ee27323551f72c4de, f-ac3599922fc1632119f54820, f-aed87e84453098245c51ee98, f-af23a2958cd7b6d97873a043, f-b5d797b986ee3066790bf6ae, f-b7d1f049c5a33441547d9f7e, f-b980363fae725dd71cb1514c, f-bb24bdd7deea407d7b9fc913, f-bc10113e0d91aab4ee16e7c8, f-bd3c0d5d28f9dfa2794e60c4, f-be8c9c9e4d4bf42476492945, f-c1661eaf3ff0a6bf1415a510, f-c2256613cafee467adf0333f, f-c5a27af694933e8c41b146f4, f-c657ba9e911ea622f7663b0c, f-c67868fa3c84839f0b411337, f-c9017fac39a744220165abff, f-ca12a8e67e54b7d5cef95591, f-cb651325fb79a036337deaa0, f-ce06fe362f5e2c21bcb6771d, f-cf13379b492a0278b00e16a2, f-d34ae54143e26b044b025db5, f-d642fbc4806bd6c7a12ff83f, f-de19700f3afa9955380a6e5e, f-de376bebd13c6edc953140dd, f-e0f9f4cd535fdef38bddd2c5, f-e0fd0e50fec281d255917fb6, f-e8b697e1f14eaaac56cb772f, f-e98dc348f08baae2e11b2511, f-ea8dbb5a6c970ba9da0d6e66, f-eb7a9c2a465763c91a1d5e51, f-ec11b456fd3257fdf32830d4, f-ec7ea8abe1edd0418a01e8a2, f-ed0a50097fdd4866579eee13, f-efb9e77a57e2ec05e73eaf32, f-f456b0e72a791b00c6174932, f-f55d409f3fddb3150b0a4992, f-f9390ce259e7164605479d93, f-fbfefc5fbb2e2f1feac12528, f-fd6daed1b92c5fc9dc97e16f

ru · official · sha256:a510ecbe26c99142783e3f74e03f65abc5455c55d4fb00f2300cee8873468257

§4. Расстояние Левенштейна Задача: по двум строкам найти наименьшее число операций вставки, удаления и замены одного символа, переводящих одну строку в другую. Вариант — таблица по длинам префиксов, как в §3. Значение состояния есть расстояние между первыми i символами первой строки и первыми j символами второй. Рекуррентное соотношение: при совпадении символов значение равно значению при (i − 1, j − 1); при несовпадении — единице плюс наименьшее из трёх: значения при (i − 1, j) для удаления, при (i, j − 1) для вставки и при (i − 1, j − 1) для замены. База: расстояние от пустого префикса равно длине другого префикса, потому что требуется ровно столько вставок. Три слагаемых отвечают трём операциям, и соответствие обязано называться: без него таблица выглядит набором формул. Стоимости операций здесь единичны; вариант с разными стоимостями меняет только слагаемые и остаётся тем же описанием, но вариант, запрещающий замену, — уже другой, и у него другое значение на тех же входах. Расстояние Левенштейна есть метрика: оно неотрицательно, симметрично и удовлетворяет неравенству треугольника. Утверждение принадлежит источнику и полезно как проверка понимания. Оценка: время и память порядка произведения длин. Известны варианты, вычисляющие расстояние за память порядка меньшей длины, и варианты, использующие ограничение расстояния сверху; они в настоящее описание не входят.

Ссылаются нормы: f-051c3e2b0f5be60c4a884dd1, f-080d96f67a63dc7bbf7c3ab3, f-094a3ffb35b3c5f2925a0f61, f-0d1bf494aa21795a531f027a, f-0f776ef17e997f92f1c01470, f-0fc03df39a3bd793beec2787, f-10270b54d36595d4fb1eb2d6, f-1175b9fd9efb68bc6ce06d29, f-1e76702497ad263293bff33d, f-20f944bdc046566941e343de, f-2109efad019ba2468d0cb7a8, f-25300018ecf5c8c651819f50, f-28ea1fa63cee1b9386323e1d, f-2d7224e64f8e422d93a8a6c4, f-314fbded13d03103803f42cc, f-31d7094a2ef8c6095bcd0ca4, f-31ec85155d79632aa62291b1, f-33f275e1f16c1c498d012b4d, f-390b54041d11f0be59179366, f-3e09f80a722713cd24d12e82, f-41d74cfb3746c0d3d753eee5, f-483a1755c36250a86549c65c, f-4ebb5828ab859eaf66850b7a, f-553e4118f0b57fdcc438f9e4, f-562c3a46640cf55fd8009466, f-5850aa7083c8364de78432f2, f-59897465b82004de90b6ae53, f-5c1dde1513f304af22391e2d, f-5d62d653de707606e2857107, f-5e7a20f783db3e1a22d3035f, f-5eb049a179cc7d578b104a39, f-5ef4b1cbb97db9c2559b893d, f-6071acb4151ebe032f15db33, f-6202262bceead60418da1586, f-684ec0f6aeecff288eefbce8, f-6a8b446319963b353862fd00, f-6bf1bf4a8a3efb85668adba3, f-6ef8d7a68a1ed987469eeda6, f-703f3c196cd3c5e93e5442d9, f-72437db41715a49b221d5ffa, f-73fe49f6e3dae27a378e0d57, f-784a0762a4f0a379bb5bf824, f-7da276c7bc61269f17d4f30f, f-7e98ca90f1080d6ba4f17d2a, f-88fddacb5d4ae10ad7a78ce4, f-8a260c70e4051714104ecc51, f-8a9d3c00cf213700c45f6d59, f-8b6af890be3143916fe5ef92, f-8bdc9fed17afe3d821daa036, f-8c95e67c83e811d4a6ccccee, f-8ce4babf792cabb38f2babb5, f-90a740da2e2732000d42a6a7, f-919e9d09cd4551f1a1b466f9, f-92776320922afa8e17e9c681, f-928c1da77172ec9301a0ba76, f-93406b90ed83eb36884d38b3, f-9558ec371c124b8175db952a, f-982cb76711b9d825818ce466, f-9b53ccc6f55bc51331d5b318, f-9ca34b09ef2fa108fcffe705, f-9e5c30e22c2cf4eaead50d4f, f-9efc4484dd202855e1a74916, f-a20be084a119f2716c2a380a, f-a29b1dca317854b79e61b6eb, f-a2ad36ded1a1a0cdc6bb5048, f-a42d664a3022200ae829184f, f-a609edb8d7173f0ea509acd2, f-a681819d88ac1722dc67994f, f-a7aaa1bbc5100eccef939450, f-ad981143acbdc417c4964e16, f-b10821ebfe8d84c65ccc8966, f-b1c9fbeda1f9d443ad716ec9, f-b471f73996cd74c1e2cfead1, f-b517eb36eed909184ae5b3b0, f-b5c0971258ce12f2d6a50399, f-b5f2822155388709b50de8a3, f-bba9b8cde4e99cad2a9dcedb, f-c07494970f573db46e59c0ed, f-c281d58a251cd11ab764b249, f-c4f2b3b4ea1c2fb703e7ce2c, f-cda548878986646b767457cc, f-d3a6e1d8020c0c7861484060, f-d3eab95dcb3a614aa74616cd, f-d58ac4df04cc989190bf57a3, f-d762c8af3843facdb8ee07a3, f-d9fd967fb305c3188d1da3ca, f-da205b84b7b706e0a0182714, f-dd8f98d6faa9dcd65faab4d8, f-e0532b82a36e2b91e928f649, f-e2ffacfb347d5f1db34c52d1, f-e806706ae87642b040df6424, f-eb5019486e38c0a23bb515b2, f-f52a11d217968965fbd859ef, f-f9c54831b393d5d8a4a8d060, f-fe1f8f44e3f12b2c0081a131, f-ff54ad94d2d71c35c689e88b

ru · official · sha256:c42b68209eb9ea5adaa7ff18d4d27138cba06b587d1dcaab1a506a7f7e79e405

§5. Оптимальный порядок перемножения цепочки матриц Задача: по последовательности матриц с согласованными размерами найти расстановку скобок, при которой число скалярных умножений при перемножении наименьшее. Само произведение при этом не вычисляется — задача только о ПОРЯДКЕ. Размеры задаются последовательностью p из n + 1 числа: матрица с номером i имеет размер p[i − 1] на p[i]. Согласованность размеров есть предусловие. Вариант — таблица по паре границ подцепочки. Значение состояния есть наименьшее число умножений для перемножения матриц от i до j. Рекуррентное соотношение: наименьшее по всем точкам разбиения k из суммы значений двух частей и стоимости их перемножения, равной произведению p[i − 1], p[k] и p[j]. Порядок заполнения — по возрастанию ДЛИНЫ подцепочки, а не по индексам границ. Это существенно: значение подцепочки зависит от значений более коротких подцепочек, и заполнение по индексам читало бы незаполненные ячейки. Стоимость перемножения двух матриц размеров a на b и b на c равна a·b·c скалярных умножений — это утверждение об обычном умножении матриц, и оно принадлежит источнику. При других способах умножения — например, методом Штрассена — вся постановка меняется. Восстановление расстановки скобок ведётся по таблице сохранённых точек разбиения; без её хранения восстановление невозможно. Оценка: время порядка куба числа матриц, память порядка квадрата. Существует решение за n·log n, принадлежащее источнику; настоящее описание его не воспроизводит и говорит об этом.

Ссылаются нормы: f-06f7fb882b6e76d10e3e27be, f-07d3a069d992fa09b7642738, f-0daa3616109b47c3b7604ced, f-0e44ec895f8344e18cae8ed0, f-1457d8ddbd69cf1cf425801c, f-1acf5079632103cf9de55010, f-1edfe0b67bf4cd105b1cfc35, f-20461397ffd5b80b080e8364, f-206903253c85ba462468c117, f-208649a3827ddf5aed8039e8, f-22c9ee44a6d45dbaa7ad4ff2, f-265d80ee47341eac0e2640a5, f-286f606fb13151eaee82d24c, f-2881c2a3e7dfa88060b21c8c, f-2ad09b01a28ae6448cdb6aaa, f-2d5a3ffc74dae875670a6125, f-2d9650ed73026198c463fdde, f-33ba6aed3107504615a6f47e, f-352d6b4666d0f0456c7249c8, f-3739d3c19df4a463af78437a, f-386266e72e4a371cc6faca2a, f-3c98295f7c266a29070a71fd, f-416395004656d351eca598db, f-43441b07ae24b2e331895679, f-444d7fbe0aacb23ce861d2e0, f-458906059f0f71e93df32194, f-4bc7ae7100ac5bd153e67e0b, f-5095409bb3340dce77c4c72d, f-529019fa40f3c469bfe5df03, f-590ab69bbc3ec3724bbbabb3, f-5cc284a3fc51559b94b7b680, f-5f80a99195153f23c8ed1559, f-6483810842a5e5cfbde3cf19, f-6680d6277768cb56809d1e89, f-66949a6b7464d2f62554bdfe, f-66a1b34d98d1eaded0a477f2, f-6724147718361ed66aae3eb8, f-672e3aac9099aa83c30790f0, f-67c41409aa3aeac47f9f4a24, f-691e5e3085390d8da0363f19, f-69800dd8aee137362a6f0264, f-6a1874db88cd8947bfdc0cd4, f-6af9b9e7415ac767291a8ac1, f-7025ce70d6155c3f5a0c5fd1, f-70ff4c3acff981a18754ec3f, f-735fc304d6b06060456ed769, f-741d0791d8fe2b58b6d7869d, f-74a34c08c7a14b9d0dba7f75, f-7555fc5e980af1e21545ff45, f-768f6b53f416d58ba8267362, f-770234fade1dd1250dcf04bd, f-79e498a7abf8983c2fd493fa, f-7aa6754e436241839914504e, f-7acea8253642f3b5be977439, f-7b6e4036a0433643898cf0b7, f-7f0dc339df6721ff01bf80c0, f-8277fca4cc7e7fac9658cb1f, f-83d7a08fd95ec4f8a5b56fa1, f-86e0662c2883c039313cce6d, f-8ac589f2652009f5bdf69fc3, f-8bf49b44c99745adc3688add, f-8ee5e11df2bf04c1630ba046, f-901dce4f005976a58d63e73c, f-9a296d0254e310aaff4a0fc9, f-9acddf83e85f2b2f9b6b4743, f-9df29d35cada715ac12969c0, f-9f01dbb1f37438418e9236b2, f-a643aaf1c440fceb3fee1f4b, f-a97f0e1d8ccf5aba31a385ea, f-ab2722357ffd892b90963b79, f-adbce7a9768812a8c2b9d380, f-aff0b37b45d9805a2c4774ec, f-b7a716dd512b8ba97dccb931, f-b8d7bf4d7edd1c572cedf53a, f-bca24a88cc96f09977c9c36e, f-bd22d08ed094d877032cc201, f-c1122a8e51233d7d34312115, f-c7ddd3d46541cbd0f69032c4, f-cab3428d3929a7f7f0ce2851, f-ccea285726573de83e7857f7, f-cec5197d7716ae203df7bac2, f-cfef9261e025ae35df295272, f-d69f310494ecc687095273c9, f-d6f5be4bad87152e216e2224, f-d8967735216a849051e38285, f-db574f4866ac524e1909fe47, f-dd469779d2b9cb2c76485b23, f-e189d62bb5fd2ba4452597b7, f-e69d08003c8f4f6c4aa542b4, f-e98e0fbfecfc55bc7c0f1529, f-eaefb06ca63d09f3a39053c1, f-edf109d804e271a36fce3441, f-f3ebf361c29ce087ef8ffae5, f-f5d5cbe28502caac5be92980, f-f8618ab96bde28d63d07506c, f-f9c8867da9eae9fc2331e482, f-fbb764e50d755252124a374a, f-fdbfb3e34b4171fddee4c850

ru · official · sha256:fb09fd11329f6e4bf1e160a4fe392778826ea7e6066c15044ff7bffe922090e1

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ: РЮКЗАК, НАИБОЛЬШАЯ ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, РАССТОЯНИЕ ЛЕВЕНШТЕЙНА И ПОРЯДОК ПЕРЕМНОЖЕНИЯ МАТРИЦ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство четырёх алгоритмов динамического программирования: рюкзака 0/1, наибольшей общей подпоследовательности, расстояния Левенштейна и оптимального порядка перемножения цепочки матриц. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни одна таблица здесь не заполняется.