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?

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.

"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

> "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 :).

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 :).

It's a NPC problem.