I can't memorize, but somone said that it's NP - problem...?

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...?

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??

"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??

> "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??

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.