Обсуждение:Задача о рюкзаке (KQvr';yuny&{g;gcg k jZt[gty)

Перейти к навигации Перейти к поиску

хм... мне кажется, или dp[w] = std::numeric_limits<int>::min(); должно быть dp[w] = 0; 83.243.71.141 19:27, 22 апреля 2010 (UTC)[ответить]

Более того, текущий вариант алгоритма решения задачи о рюкзаке с повторами будет некорректно работать, к примеру, если все веса вещей - четные, а вместимость рюкзака - нечетное число. И алгоритм вернет std::numeric_limits<int>::min(); в этом случае. Правильным было бы инициализировать dp[w] = dp[w - 1]. Ведь мы можем набрать туже стоимость и при весе большем на единицу. И это согласуется с логикой динамики, описанной в статье - "Обозначим через Kw максимальную стоимость, которую мы можем набрать при весе не более w". Eik0u 18:22, 14 июля 2010 (UTC)[ответить]

Не знаком с данной задачей на практике, но почему нельзя просто подсчитать удельную стоимость для всех вещей и складывать их, соответственно от самой большей до самой меньшей в рюкзак? 17:48, 11 ноября 2011 (UTC)

Потому что это Может не дать самый оптимальный результат.
Например, такая задача. Есть три вещи, их веса 1, 3 и 2, а цена 3, 6 и 5 соответственно. И у нас ограничение по вместимости 5. Тут, используя удельную стоимость, вы не получите самый оптимальный результат. 37.17.113.147 09:55, 19 июля 2012 (UTC)[ответить]

Рецензирование статьи Задача о ранце

[править код]
Здесь находятся завершившиеся обсуждения. Просьба не вносить изменений.

Хочу довести статью до статуса хорошей(в идеале избранной). Особенно интересуют замечания по части криптографического раздела статьи.LubaMar 16:11, 10 октября 2012 (UTC)[ответить]

  • В статье приведен список литературы, однако судя по сноскам он при написании статьи никак не использован. Филатов Алексей 13:47, 10 октября 2012 (UTC)[ответить]
    В сносках имелись книги их списка литературы: Б.Шнаер (1), А.Соломаа (5). Добавила сноски на 2 другие книги (ссылок на них у меня нет, есть только печатный вариант). Первые три книги и списка литературы были до моего вмешательства, как и последний абзац о возможности бесконечного выбора предметов. Я этой литературой не пользовалась и сноски из нее делать не могу. Имею ли я право ее убрать?LubaMar 20:56, 10 октября 2012 (UTC)[ответить]
    Убирать не нужно, нужно оформить соответствующим шаблоном {книга}, а ссылки на использованные вами книги - при помощи шаблона {sfn}. Примеры оформления - практически в любой избранной статье, получившей статус недавно. Филатов Алексей 08:00, 11 октября 2012 (UTC)[ответить]

переоформила ссылки на примечание по образцу из избранной статьи, а вот насчет книг не поняла. Мною был использован шаблон {книга}, он не тот? {sfn}-не нашла его к сожалению, не подскажите пример статьи с ним? Буду очень признательна.LubaMar 21:10, 10 октября 2012 (UTC)[ответить]

1.преамбула
2.Классическая постановка задачи
 2.1 Разновидности в математике
 2.2 Разновидности в криптографии
3.История
 3.1 NP-полнота
 3.1 в криптографии
 3.2 в математике
4. Решения
 4.1 точные решения (тут как и раньше полный перебор, етви и динамическое програмирование)
 4.2 приближенные решения (жадный алгоритм)
 4.3 метаалгоритмы (генетический)
5. Применение в криптографии
 5.1 Коротко идея (название пока не очень)
  5.1.1 легкая проблема
  5.1.2 сложная проблема
 5.2 Шифрование
  5.2.1 Создание открытого ключа из зактрытого
 5.3 расшифрование
5.4 криптостойкость
 5.4.1 секретная лазейка
6. будущее рюкзачных систем.

Близко по структуре к странице о рюкзаке на французском(по крайне мере я пыталась уподобиться). Если это плохо, то посоветуйте как лучше. LubaMar 19:45, 13 октября 2012 (UTC)[ответить]

  • Не дождалась вас. Так что сделала по этому плану. Добавила много ссылок на источники, описаний к рисункам, описаний к алгоритмам. Попыталась написать историю, надеюсь стало лучше. LubaMar 15:04, 14 октября 2012 (UTC)[ответить]
    Уже лучше (структура мне в общем и целом мне нравится, но детальнее я смогу сказать только после прочтения статьи). Сейчас в глаза бросается наличие абзацев без единого источника, некорректно оформленные источники (например, ссылка №10 - это что и на какой странице информацию искать?). Также необходимо посмотреть источники на предмет дополнения статьи (сейчас там бросается в глаза обилие формул, слабо разбавленных текстом), что у неподготовленного пользователя наверняка отобьет охоту ее читать. Поймите, что читатель, который придет сюда читать вашу статью, вряд ли знает что-то кроме названия. А вы ему фактически подсунете конспект лекций. Например, постановка задачи у вас хорошо написана доступным языком лишь в описании первой картинки, а в тексте же начинается сразу с ее описания математическим языком. Далее перечислены варианты, которые никак не описаны. Очевидно, что уже первый же раздел ("Постановка задачи") можно более обширно и толково описать, а не дать формулу и два списка. Филатов Алексей 16:38, 14 октября 2012 (UTC)[ответить]
  • Итого, предлагаю действовать последовательно: напишите как следует (т.е. чтобы развернуто и понятно) первый раздел про постановку задачи. Когда закончим с ним, то перейдем к следующему и т.д. А иначе мы еще долго дискутировать сможем. Филатов Алексей 16:38, 14 октября 2012 (UTC)[ответить]
    насчет ссылок: плохо то что некоторые не кликабельны? в некоторых не отображается язык,хотя он указан в шаблоне. не знаю почему. Далле, насчет классической поставноки, описание на уровне укладки ранца в поход я дала в преамбуле. Раздел классическая постановка по моим соображением должен дать строгое математическое определение, оно короткое и ясное, никаких особенных знаний выше школьной программы не требует. Что к нему можно добавить я не знаю, в любой книге(в источниках) такая формулировка. Подробнее разновидности рюкзаков написать сложно, но можно.LubaMar 21:52, 14 октября 2012 (UTC)[ответить]
    По оформлению ссылок на источники читайте ВП:СН. Что касается "описание на уровне укладки ранца в поход я дала в преамбуле", то преамбула - это краткий пересказ всего содержимого статьи (иногда для того, чтобы не читать всю статью). Вы же пытаетесь использовать ее в качестве как первый раздел, а не обзорный, что неправильно. Ну а насчет "строгое математическое определение, оно короткое и ясное", так можно и в качестве описания фильма дать лишь технические параметры изображения (они тоже "короткие и ясные") - будет ли этого достаточно? Филатов Алексей 18:55, 14 октября 2012 (UTC)[ответить]
    Спарведливо. Оформление ссылок в тексте поправила(положение относительно знаков препинания), все ссылки с языком и кликабельны (кроме книги 1974 года, пока не нашла ссылку). Заметила, что в некоторых избранных статьях нет раздела литература, его успешно заменяют примечания. В моем случае помойму можно тоже так поступит и литературы упразднить? описание задачи дополнила, перечень пояснила. Перечень относящийся к криптографии убрала ниже, его нельзя пояснить без знаний из раздела «задача о ранце в криптографии».LubaMar 10:39, 15 октября 2012 (UTC)[ответить]
    На странице обсуждений (СО) избранных статей (ИС) должна быть указана дата избрания. Когда выбираете себе статью для примера, то смотрите, чтобы статье был присвоен статус в этом году. Дело в том, что требования к оформлению статей ежегодно растут и, например, те статьи которые избирались в 2010 году, сейчас уже вряд ли будут избраны (без доработки). Филатов Алексей 11:08, 15 октября 2012 (UTC)[ответить]
    Ну вроде ссылки переоформила, теперь книжки подсвечиваются))) и страницы видны. Кстати теперь математическая формулировка по-яснее выглядит?LubaMar 22:18, 15 октября 2012 (UTC)[ответить]
    Вот если говорить о разделе "Классическая постановка задачи" (пока лишь о нем), то уже все хорошо. Единственное, неплохо было бы указать, кто именно и в каком году сформулировал такую трактовку задачи (ныне именуемую "классической"). Филатов Алексей 18:50, 15 октября 2012 (UTC)[ответить]

История

[править код]
  • Здесь следующая проблема изложения: вы дав только постановку задачи и не рассказав ничего про ее изучение, сразу сообщаете читателю о том, что "в 1972 году данная задача вошла в список К.Мэннига NP-полных задач". Поверьте, большинству читателей это не скажет ровным счетом ничего. Дальше - больше: вы сразу начинаете рассказывать про изучение задачи в криптографии (при этом еще не рассказав ничего об истории изучения самой задачи!). В общем, историю надо строить ровно наоборот: сначала историю изучения самой задачи и алгоритма, потом уже - прикладное применение. Филатов Алексей 18:50, 15 октября 2012 (UTC)[ответить]
    Я наверху вам ответила насчет автора: Информация об этом есть в английской википедии. Их ссылки не дают скачивать источники (их можно только купить). Поэтому проверить эту информацию сложно. Один источник удалось скачать, но там я не нашла указанной информации. LubaMar 15:24, 14 октября 2012 (UTC).
    Далее, в написании истории я старалась смотреть на французскую страницу, и там сразу сказали про NP-полноту, потом про криптографию(конечно не так развернуто, как у меня, но мне так нужно(упор на криптографию), а потом уже другие разделы. Может стоит не выделять NP-полноту отдельно (раз я не заостряюсь на ней, а внести ее в изучение в математике. а потом криптографию вторым пунктом?LubaMar 20:08, 16 октября 2012 (UTC)[ответить]
    можете посмотреть результат. И если уж писать про первопроходцев, можно ли цитировать другую страницу вики(французскую), ведь проверить их источники я не могу.LubaMar 20:33, 16 октября 2012 (UTC)[ответить]
    Про французскую страницу: та статья во фрВики была избрана в 2006 году. С тех пор многое сильно поменялось. Поэтому брать ее за образец уже не стоит. Филатов Алексей 17:50, 16 октября 2012 (UTC)[ответить]
    Пример статьи с образцово оформленными ссылками на источники (в том числе при помощи шаблонов {sfn}): Ганнибал. Филатов Алексей 17:58, 16 октября 2012 (UTC)[ответить]
  • Про источники: по-хорошему, вы должны писать по источникам самостоятельно, а не ссылаться на книгу только потому, что на нее ссылка в енВики указана. Во-первых, сама Википедия и ее статьи для других статей не является АИ (по определению), а, во-вторых, мне уже доводилось выверять одну статью, переведенную из енВики - в итоге была обнаружена просто прорва ошибок и неточностей. Филатов Алексей 18:02, 16 октября 2012 (UTC)[ответить]
    я использовала фр. статью как образец структуры(помойму информация с годами испортится не могла),плюс именно про то что я не могу тупо списывать с нее я и говорила, а ссылки статьи на нглийском не позволяют скачать и проверить сказанное там про автора классической формулировки! Итог, автора формулировки в своих источниках я не нашла, так что пока придется обойтись без него. истрию я перекомпоновала, стало ли лучше? П.С статью про ганибала я и смотрела при оформлении ссылок.)LubaMar 20:33, 16 октября
  • Ссылку на пиратские сайты уберите (я про ebookee.org и иже с ним). Филатов Алексей 15:10, 17 октября 2012 (UTC)[ответить]
  • С оформлением первой ссылки проблема: кликаю на "Silvano, 1990" и ничего не происходит. Филатов Алексей 15:10, 17 октября 2012 (UTC)[ответить]
  • С историей пока что далеко не все благополучно: вот, смотрите, у вас первый же подраздел в истории называется "Изучение в математике", а далее уже просто говорится "Задача о ранце интенсивно изучалась, особенно в 70-90-е годы 20-ого века, как теоретиками так и практиками". Возникает вопрос: а эта задача впервые была поставлена математиком? Если да, то кем и когда? Если нет, то где эта задача вообще возникла? Здесь, даже если на этот счет ничего толком не известно, все равно надо как-то толково начать историю. А сейчас, если можно так выразиться, у вас повествование начинается со середины книги "Властлин колец" при полном отсутствии первой половины. Филатов Алексей 15:16, 17 октября 2012 (UTC)[ответить]
    Толкину было куда легче, ему не надо было ссылаться на каждую букву) Тем более не приходилось искать хакнутый источник и вообще он мог писать все что угодно. Я обыскала все и вся, бесплатно статью не скачать, следовательно проверить английскую вики я не могу. Поэтому напишу как это сделали все остальные страницы(языки).LubaMar 20:37, 17 октября
    Гляньте сколько книг существует по данной теме. То есть, данному алгоритму полностью посвящены как минимум две книги (Silvano и Kellerer). Соответственно, написать одну вменяемую статью вполне можно. А если учесть, что данный вопрос рассматривается в куче других книг, то вообще - песня. Филатов Алексей 06:31, 19 октября 2012 (UTC)[ответить]
    спасибо за очевидный совет(думаете я там не была). Вы не учитываете что в основном эти книги не по криптографии, а значит особо не полезны для моего дела. Плюс Сильвано и Келлера я читала(вторую полностью скачать не возможно, только отдельные не полезные для меня главы, а покупать ее желающих нет),(если любопытно посмотрите сколько строчек Сильвано уделил исторической справке. никакого создателя формулировки там нет, как и в тех что я еще просмотрела.) Забить в поисковик название проблемы легко...
    Я ведь исправила, теперь есть ссылка на одного первопроходца...зачем ругаться то. Больше у любознательного читателей вопроса о создателе не возникнет...дайте пожалуйста новый вопрос)))LubaMar 22:28, 19 октября
    Вы не учитываете что в основном эти книги не по криптографии, а значит особо не полезны для моего дела - вы пишете статью о задаче в целом, а не о её конкретной реализации в криптографии (см. ВП:ВЕС). Это означает, что данную задачу надо описывать со всех сторон, а не только лишь ее применение в криптографии. Основные области ее применения (насколько я на данный момент знаю) - это математика, криптография и программирование. Соответственно, применение задачи в этих дисциплинах должно быть описано в равной (условно говоря) мере. Кстати, по поводу ее реализации и использованию в программировании выложены конспекты лекций нескольких университетов. Филатов Алексей 19:09, 19 октября 2012 (UTC)[ответить]
  • Замечание общего характера: там где в тексте статьи присутствуют ссылки на другие статьи РуВики еревод указывать не нужно (он есть в соответствующей статье). Например, даете ссылку на статью Ади Шамир, при этом транскрипцию имени ученого на английском языке приводить не нужно, тем более, что он работает в Израиле, а не в англоязычной стране. Во-вторых, оригинал ФИО дается на родном для человека языке (т.е. как он при рождении был назван) и как его зовут в той стране, где он сейчас работает (если он эмигрировал куда-то). А сейчас вы всех независимо от национальности указываете на нглийском языке, что неправильно. Филатов Алексей 19:09, 19 октября 2012 (UTC)[ответить]
  • Можно создать раздел "Ссылки", где дать ссылки на какие-нить дополнительные материалы, которые не были использованы в статье в качестве источников (например, вот эта видеолекция или вот этот целый сайт, посвященный данной задаче). Филатов Алексей 19:13, 19 октября 2012 (UTC)[ответить]
  • Вот здесь говорится, что задача была описана в 1957 году, что и положило начало ее изучению. Филатов Алексей 19:46, 19 октября 2012 (UTC)[ответить]
    вот тут не состыковка. В других страницах вики настойчиво говорят о дате 1897, а вы говорите о 1957...разница есть. кому верить? Далее видео к сожалению не работает.LubaMar 19:08, 20 октября
  • В общем, я порыскал в Интернете и выяснил, что данной задаче посвящено множество научных работ и данная тема весьма обширна. Соответственно, предлагаю начать с чего-нить более конкретного: например создать статью-список видов задачи (нечто наподобие этой статьи) и довести ее статуса избранного списка. Филатов Алексей 19:46, 19 октября 2012 (UTC)[ответить]
    Этого я сделать не могу. Список я сделала в самой странице, можете посмотреть на результат. Надеюсь не плохо вышло. Тема то обширна,но почти все книги по ней перепевание друг друга)(математика), в информатике не знаю, в криптографии к сожалению тема свое отзвучала. Веб страница эта конешно милая, но книгам я верю больше , ссылки сделаю...может и правда полезноLubaMar 20:44, 20 октября
    не большой вопрос. Мне проверили правки и в случае с азиаткими именами указали некие comment, что мне с ними делать?LubaMar 20:57, 20 октября
    что мне с ними делать - с ними - ничего. Нужно исправить в статье транскрипции имен (помимо ошибок указания оригинальных имен). Филатов Алексей 19:28, 20 октября 2012 (UTC)[ответить]
  • Этого я сделать не могу - почему? Давайте выделим список в отдельную статью, доведем ее до приличного состояния и вы выдвините ее на получение статуса избранного списка? Филатов Алексей 19:28, 20 октября 2012 (UTC)[ответить]
    потому что у меня есть задание) то что я написала в статью(список) с лихвой покрывает тот список на английском, кроме рюкзакоподобных задач. Насчет всех имен на английском, не думайте что я не знаю , что все это не агличане и американцы)))просто на самом деле ценность их имен иероглифами равно 0) ведь все статьи которые они сами пишут, они подписывают именно теми англискими именами, что я написала. Иначе их просто нельзя найти в гугле и кто вообще запомнит человека, чье имя написано не понятными символами и не имеет звучания на английском. Когда я пишу статью на заграничную конференцию я же не пишу свое имя на русском...так что для удобства читателя(то есть если он захочет найти статью именно данного китайца, японца, немца...) я пишу имена на английском. а иероглифы искать...ну это трата времени в пустую, при всем моем уважении к этим людям. Так что ошибкой свои действия не считаю, разве что транскрипция на русском могла быть не удачной(так лучше бы проверяющий и поправил, а не говорил, что это ужасно, раз владеет языками этой группы)LubaMar 11:35, 21 октября
    лучше бы проверяющий и поправил - а еще лучше сам и написал бы статью? :) Боюсь, что с таким подходом к написанию статей у вас возникнут проблемы с доведением их до статуса ХС или ИС. "Задача о ранце" из-за объема будет представлять собой по сути целый кластер статей, а основная статья должна быть по сути обзорной. А написание обзорной статьи - не слишком простая задача (даже опытные участники берутся за такое неохотно). Вы же бестолково все понапихали в одну статью и рекомендаций не слушаете. Соответственно, если считаете, что статья и так хороша, то закрывайте это рецензирование и выдвигайте статью в кандидаты в хорошие статьи. Филатов Алексей 10:16, 21 октября 2012 (UTC)[ответить]
    да не считаю я ее хорошей, и писать за меня ничего не надо(можно было просто правильно написать имена раз владеешь языком). Я слушаю те рекомендации которые могу исполнить не выходя за рамки данного мне задания. И я честно считаю что в случае с именами это потеря времени на то, что никому не нужно. Я же поправляю историю, ссылки, формулы, картинки, структуру...все то что хоть как-то можно классифицировать важным(имею же я право не поправлять эти имена, раз считаю что вы заблуждаетесь и английское имя под которым человек печатается нужнее) А если уж статья такая бестолковая...то ну и пусть, зато содержательно, а не с водой вместо формул и теорем. Нужен отдельный список, будет...надеюсь после этого мы продолжим улучшать статью дальше)LubaMar 15:48, 21 октября
    список, теперь я могу на него ссылаться?LubaMar 16:19, 21 октября
    Да. В основной статье оставьте только "классическую постановку задачи", а сразу после названия подраздела добавьте сылку на этот список при помощи шаблона {main}. В список добавьте еще интервики (ссылку на аналогичный список в енВики). Филатов Алексей 12:30, 21 октября 2012 (UTC)[ответить]
    добавила. В самой статье даже список убрать?LubaMar 16:38, 21 октября
    Нет, оставьте так. Добавьте только пробелы перед скобками в списке в основной статье. Филатов Алексей 12:52, 21 октября 2012 (UTC)[ответить]
    выполнено. что дальше?LubaMar 17:26, 21 октября
  • В раздел "История" добавьте еще раздел об изучении задачи в биологии (видел в интернете публикации на эту тему) и упомяните там про "генетический алгоритм", а также изучение в информатике. Филатов Алексей 18:32, 21 октября 2012 (UTC)[ответить]
    это что-то новенькое для меня. помоему наоборот, для решения задачи о ранце используют биологические модели, а не наоборот. Добавила в ссылки к генетическому алгоритму несколько статей на эту тему. LubaMar 9:12, 22 октября
    Тут главное показать, что задача изучается и в биологии/генетике. Филатов Алексей 06:34, 22 октября 2012 (UTC)[ответить]
  • В дальнейших разделах от фраз в стиле "Применим открытый ключ B и зашифруем..." нужно отказаться, т.к. в Википедии принят стиль повествования от третьего лица, а кроме того все руководства отсюда удаляются. Филатов Алексей 18:32, 21 октября 2012 (UTC)[ответить]
    немного поправила, но конкретно эту фразу не знаю как заменить от третьего лица, все-таки это пример.LubaMar 9:36, 22 октября
    Ладно, до нее еще дойдем. Потом решим. Филатов Алексей 06:34, 22 октября 2012 (UTC)[ответить]
  • Вы не хотите выделить изучение задачи в криптографии в отдельную статью? Это позволило бы сконцентрироватсья только на криптографии, а так придется писать про всю область применения задачи (хоть и кратко)? Филатов Алексей 06:34, 22 октября 2012 (UTC)[ответить]
    идея хорошая, как со списком и сослаться на нее да?...наверное и правда будет не так громостко. Кстати, насчет 1897 года в котором Мэтьюс написал свою статью, которую никак не скачать. Мне знакомый прислал скан книги Hans Kellerer, Ulrich Pferschy, David Pisinger «Knapsack Problems»( ее на гугле можно скачать только частично, 1 главу в конце) где об этом сказано, самое начало. За границей такие книги достать легко в институтской библиотеке) Так что я могу теперь с полным правом сказать о нем как о первопроходце. Проблема с автором задачи решена. LubaMar 13:19, 22 октября
    как со списком и сослаться на нее да? - да, именно это я и предлагаю. :) Филатов Алексей 09:25, 22 октября 2012 (UTC)[ответить]
    Убрать в новую статью подробную историческую справку, и все алгоритмы. А что оставить от нее в исходной статье?LubaMar 13:27, 22 октября
    Да, все, что относится к криптографии. В самой статье сделать раздел с каким-нить названием навроде "Изучение в дисциплинах", а там в качестве подразделов создать разделы "Изучение в математике", "Изучение в математике", "Изучение в информатике" и "Изучение в биологии". Что касается криптографии, то в данной статье должно остаться краткий пересказ выделенной статьи, т.е. немножко исторических сведений, постановка задачи в криптографии, кратко описать основные алгоритмы и практическое применение (опять-таки, в криптографии). Филатов Алексей 09:51, 22 октября 2012 (UTC)[ответить]
    Сейчас я занята...надеюсь в ближайшее время сделать это изменение.LubaMar 19:17, 27 октября
    ну вот, я разделила страницы. пока выглядит очень сыро наверное. что где добавить/убрать?LubaMar 10:33, 28 октября
  • Ну вот, постепенно статья таки обретает ясность. Но почему алгоритмы вы отнесли исключительно к информатике, ведь вы там указываете и на существование метаалгоритмов, а значит они не привязаны к определенной науке. Соответственно, предлагаю их выделить в раздел "Алгоритмы". Филатов Алексей 08:44, 29 октября 2012 (UTC)[ответить]
    мнеказалось что метаалгоритмы еще одно новое направление в информатике? к биологии они имеют лишь то отношение, что модель взята биологическая. но задач по биологии они не решают в данном случае.LubaMar 18:43, 29 октября
  • Картинку с блок-схемой лучше уменьшите (после названия файла укажите его желаемый размер, например: [[Файл:Генетический алгоритм.png|200px|thumb|right|Блок схема генетического алгоритма]]. Филатов Алексей 08:44, 29 октября 2012 (UTC)[ответить]
    спасибо, сделано.LubaMar 18:50, 29 октября
  • Какую из статей предпочтете дорабатывать - эту или Задача о ранце в криптографии? Филатов Алексей 08:45, 29 октября 2012 (UTC)[ответить]
    криптографию естественно) что исправлять?LubaMar 18:43, 29 октября
  • Про раздел "Изучение в биологии" забыли. Филатов Алексей 08:47, 29 октября 2012 (UTC)[ответить]
    мне туда писать нечего...раздел создать могу конешно, но заполнить...LubaMar 18:44, 29 октября
  • В общем, если предпочитаете дорабатывать статью про криптографию, то данную страницу рецензирования закрывайте и открывайте новую, но уже для статьи про криптографию (не забудьте на СО статьи её добавить). Продолжим уже там. Филатов Алексей 14:52, 29 октября 2012 (UTC)[ответить]

Ошибка в разделе "Применение динамического программирования"

[править код]

В качестве решения методом "Динамического программирования" (ДП) описан метод "Ветвей и границ", ничего общего с ДП не имеющим. Robert.ayrapetyan 01:22, 12 января 2014 (UTC)[ответить]

Удаление раздела про генетический алгоритм

[править код]

Большой раздел, который имеет слабое отношение к статье. Описание алгоритма есть на соответствующей странице. И если предыдущие алгоритмы предлагают способы решения задачи о ранце, то связь с этим можно выразить как "в генетическом алгоритме есть задача о ранце", при этом постановка задачи остается неясной. В задаче о ранце вместимость рюкзака - некоторая константа, а не целевая функция. Большой акцент на описании алгоритма, а не связи с задачей. В конце даже присутствует его оценка "Генетический алгоритм не гарантирует нахождения оптимального решения, однако показывает хорошие результаты за меньшее время по сравнению с другими алгоритмами[21][22]." При этом, обычно генетические алгоритмы используются как раз для решения этой задачи, и если добавить информацию об этом, то информация будет противоречить. — Francisso (обс) 16:26, 16 октября 2016 (UTC)[ответить]

  • Вообще-то в этом разделе было описано применение генетического алгоритма именно к задаче о ранце. Кроме того раздел был написан по АИ. Возможно это раздел стоило улучшить сделав акцент на эту задачу, а не на общее описание алгоритма, но удалять его, по-моему, не стоило. — Алексей Копылов 02:41, 18 октября 2016 (UTC)[ответить]

Название статьи

[править код]

Задача более известная как «задача о рюкзаке», чем «задача о ранце», к тому же далее везде употребляется именно слово «рюкзак». Полагаю, стоит переименовать. Не смотря на то, что в англовики используется слово knapsack, а не backpack, стоит всё-таки опираться на популярность названия в русском языке. Richard Try (обс.) 08:11, 3 декабря 2018 (UTC)[ответить]