[задача про рюкзак] [оптимизация] Возможно ли?

Бро, дискретные множества, обычно, не выпуклы, поэтому мы часто не можем точно решить эти задачи. Например, если ты будешь использовать принцип минимальной длины описания, то по-хорошему у тебя будет регуляризация типа f(x)+ len(x), выпуклой оболочкой этой поебени будет l1 норма x. Вот задачи с l1 нормой мы вроде почти научились быстро решать.

Ещё одно молодое дарование, не читающие условия задачи

Отлично, и теперь давай подумаем, зачем нам рассуждения о «задачах над вещественным полем», если у нас задача — дискретная?

Ответы не читай @ Дальше вопрошай.

Можно вопрос: ты где, когда и на какой специальности учился? Курс теории оптимального управления был? Курс теории оценки сложности алгоритмов был?

А ты не знаешь матчасти.

Специально для Вас, поручик:

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

http://ru.wikipedia.org/wiki/NP-полная_задача

http://ru.wikipedia.org/wiki/Шаблон:NP-полные_задачи

http://ru.wikipedia.org/wiki/Задача_о_ранце

Ещё раз, для молодых, амбициозных и одарённых, давай по порядку.

Дай определение «определена над полем вещественных чисел» и «все хорошо».

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

блин, ушёл ставит фолаут.

210100 учился на заочке

А вот зачем. У вас по-моему склероз на фоне маразма(с), сэр. Задал вопрос и удивляется зачем отвечают на него.

Если стоимость/вес или количество предметов в рюкзаке (обычно первый параметр) могут принимать вещественные значения, то эта задача может быть решена за полиномиальное время. В случае целочисленных значений быстрого алгоритма ее решения не существует. Выше уже объяснил kombrig, почему.

А вообще не худо бы тебе перестать быть Ъ и сходить по ссылкам. А еще подучить теорию оценки сложности алгоритмов.

А ты не знаешь матчасти.

Нахера ты тут об этом вообще пишешь? Преподу своему будешь это все рассказывать.

Если стоимость/вес или количество предметов в рюкзаке (обычно первый параметр) могут принимать вещественные значения, то эта задача может быть решена за полиномиальное время.

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

Я это ТСу рассказываю, дабы избавить его от головной боли.

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

Ты конечно можешь считаь вес крупинки или кол-во капель, но, это неоправланное расходование вычислительных ресуросов.

К примеру, при планировании закупок овощебащы тебе ни кто не будет заморачиваться весом отдельной картофилины, а будут даны макс объем, спрос в предыдущем периоде , сколько сгнило. И ты можешь считать что ты можешь купить 1.353465346876598569т морковски и не парить себе мозг кто морковка весит 0,00005т

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

Угу, только решение тут уже напихать одного самого дорогого товара.

А если ввести сроки реализации товаров и штрафы за протухший товар?

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

Напоминает подобный диалог (и ещё про дельфины и блох):

Q: Как быстро забивать гвозди в доски, чтоб они не гнулись?

A: Если нужно забивать дюбели, можно пользоваться пистолетом и будет быстро.

A: Бери дрель, сверли отверстия и потом шуроповёртом заручивай шурупы.

A: Не, болты или шпильки рулят.

И так в цикле. И, что характерно, по теме так ничего и не прозвучало.

И так в цикле. И, что характерно, по теме так ничего и не прозвучало.

тебе тут каждый 2ой писал про NP полноту и то, как это относится к твоей задаче. Я вобще не пойму, почему при таком хамском отношении и нежелании читать ответы, и абсолютно бестолковой постановке задачи, тебе всё ещё отвечают.

Я спрашивал о полноте? С каких пор моя задача? Кого волнуют классы других задач в этой теме?

> > И так в цикле. И, что характерно, по теме так ничего и не прозвучало.

Спок, бро. Ты понял вообще что я тебе написал про выпуклость? Многие задачи специально релаксируют из домена {0,1} в [0,1]. А потом, найдя решение на отрезке, проецируют его на куб.

Вот пример http://en.wikipedia.org/wiki/Linear_programming_relaxation

«the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1].»

ну и далее, просто прямым текстом написано «This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming)».

Такие приемы часто используются сегодня везде и всюду. Я активно работал с граф-катами и level-set методами.

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

Спрашивали о наличии быстрого решения задачи, я указал границы его существования. Что еще надо?

И тем не менее, все это не имеет никакого отношения к вопросу «можно ли решить эту задачу быстрее?».

Спрашивали о наличии быстрого решения задачи, я указал границы его существования. Что еще надо?

Аналогично ^

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

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

Здесь явно речь идет о олимпиадной задачке. Тут интерес чисто теоретический и нужо именно точное решение.

ну это ты так решил)