Discussion @ 1115. Ships @ Timus Online Judge

I don't know how to solve it.

Posted by Sun-ho, Cho 29 Dec 2001 06:44

I don't know how to solve this problem.
Give me some hints please.

Happy new year.

Me too at the first time.

Posted by Huang Yizheng 29 Dec 2001 12:48

If you want more details,you can email to "hyz12345678@163.com".

This is a NP problem

Posted by Algorist 30 Dec 2001 00:28

It is a "multi-knapsack", which is proved to be NP. So, use recursion
with some optimizations.

(NP = Non Polynomial) -> that means that there is no efficient
algorithm (well, not exactly that, but almost the same in this case)

Re: I agree with you. But to get AC is very easy.

Posted by Revenger and NSC 30 Dec 2001 16:41

Isn't complete search with a few optimizations enough? Or even, a greedy?

Posted by Algorist 31 Dec 2001 02:34

Re: I agree with you. But to get AC is very easy.

Posted by Miguel Angel 31 Dec 2001 09:29

> Could you help me?? mail:miguelangelhdz@hotmail.com, or here, i did
it, but get time limit exced :|

Discussion of Problem 1115. Ships