Discussion @ 1115. Ships @ Timus Online Judge

Sun-ho, Cho I don't know how to solve it. [5] // Problem 1115. Ships 29 Dec 2001 06:44

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

Happy new year.

Huang Yizheng Me too at the first time. // Problem 1115. Ships 29 Dec 2001 12:48

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

Algorist This is a NP problem [3] // Problem 1115. Ships 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)

Revenger and NSC Re: I agree with you. But to get AC is very easy. [2] // Problem 1115. Ships 30 Dec 2001 16:41

Algorist Isn't complete search with a few optimizations enough? Or even, a greedy? // Problem 1115. Ships 31 Dec 2001 02:34

Miguel Angel Re: I agree with you. But to get AC is very easy. // Problem 1115. Ships 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