|
|
вернуться в форум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...? Послано грузик 17 авг 2009 08:57 It's a NPC problem. |
|
|