ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1144. The Emperor's Riddle

I can't memorize, but somone said that it's NP - problem...?
Posted by Nemets Ilya 19 Mar 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...?
Posted by Mephistos 19 Mar 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??
Posted by Miguel Angel 20 Mar 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??
Posted by Mephistos 20 Mar 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??
Posted by Scythe (Berinde Radu) 4 Jan 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...?
Posted by грузик 17 Aug 2009 08:57
It's a NPC problem.