ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1144. The Emperor's Riddle

I can't memorize, but somone said that it's NP - problem...?
Послано Nemets Ilya 19 мар 2002 18:12
Sorry, but I don't beleive in such a simple solution as DP.
It looks like a good heuristic, but not a real solution.

Has anyone another opinion?
Re: I can't memorize, but somone said that it's NP - problem...?
Послано Mephistos 19 мар 2002 20:31
I've just read the problem and don't know the solution, but I can
suppose that the point is that all wheights are whole numbers. I
think it's like the problem about the bag (given the set of things,
each of weight Wi and value Vi, find the subset with maximal value
and total weight not exeeding some number W). This is NP problem, but
in case of descrete and not very large weights it has DP solution.
Do you think so??
Послано Miguel Angel 20 мар 2002 08:52
"in case of descrete and not very large weights it has DP solution."
I saw a comment of blue cat saying that he has a DP solution about
this problem but I think it's more likely to be a good heristhic, i
wish to know how to do it. BTW there's another problem like
this, "Ships"(right now i don't remind the number) but it's more easy
to get AC than this one. (I have had TL).
mail:miguelangelhdz@hotmail.com
Re: Do you think so??
Послано Mephistos 20 мар 2002 12:09
> "in case of descrete and not very large weights it has DP solution."
I was speaking about "bag" problem. It really has DP solution.

I cannot say anyting certain about the DP solution of the subj
problem, because I don't know it :).
Re: Do you think so??
Послано Scythe (Berinde Radu) 4 янв 2003 13:16
The solution to the kanpsack (bag) problem is a DP solution, but the
time complexity is O(n*W) (W is the total weight the knapsack can
hold), and it is pseudo-polynomial. For the multiknapsack problem,
the search space is much more than O(W).
Anyway a DP solution on O(n*m) is out of the question. If it would
be a solution, that means he could solve the knapsack problem (which
is NP) in O(n) and that is impossible. I cannot begin to think how
one could solve such a problem (unless indeed one can find a
solution that is not perfect, but passes the given tests)

> > "in case of descrete and not very large weights it has DP
solution."
> I was speaking about "bag" problem. It really has DP solution.
>
> I cannot say anyting certain about the DP solution of the subj
> problem, because I don't know it :).
Re: I can't memorize, but somone said that it's NP - problem...?
Послано грузик 17 авг 2009 08:57
It's a NPC problem.