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

задан 18 Окт '17 0:02

наверное тот же класс

(18 Окт '17 0:11) abc

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

(18 Окт '17 0:12) falcao

@falcao, тут вопрос не о временной сложности, зачем нам нужен размер ввода?

(18 Окт '17 0:14) orange_borange

@abc, какой тот же? Задача о рюкзаке это NPC, а задача о рюкзаке с оптимизацией это уже NP-трудная

(18 Окт '17 0:16) orange_borange

@orange_borange сформулируйте свою задачу полностью математически. Я думаю что тогда все сразу прояснится. И что значит задача с оптимизацией и без? Типа просто укладка рюкзака и укладка с минимальной стоимостью? Это же один класс задач вроде.

(18 Окт '17 0:45) abc

@orange_borange: я пока не понял постановки задачи, поэтому мог сказать что-то не соответствующее её характеру. Но моё замечание касалось следующего: когда задают узкоспециальные вопросы, не переводя их на общепонятный язык, то этим уменьшают шансы, что кто-то поучаствует в обсуждении.

(18 Окт '17 1:48) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×72

задан
18 Окт '17 0:02

показан
233 раза

обновлен
18 Окт '17 1:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru