Discussion @ 1115. Ships @ Timus Online Judge

How to solve this problem? Is it a NP problem?

Posted by Saturn 5 Jul 2004 15:22

How to solve this problem? Is it a NP problem?
Thanks

Re: How to solve this problem? Is it a NP problem?

Posted by Saturn 5 Jul 2004 23:54

I used full search and got TLE#5

Read the problem carefully.You must be missing some important describe.By the way,DP+DFS will work...good luck!

Posted by Yu YuanMing 7 Jul 2004 09:22

I think the problem is NP (+)

Posted by Dmitry 'Diman_YES' Kovalioff 7 Jul 2004 17:31

It is one of knapsack-problem's variations, which is obviously NP. I used brute force with some optimizations and got AC within very short time. Of course, DP will work because of weak restrictions, but brute force is a classical way to solve this problem.

Edited by author 07.07.2004 17:33

Re: Read the problem carefully.You must be missing some important describe.By the way,DP+DFS will work...good luck!

Posted by Saturn 8 Jul 2004 00:08

Can you give me more details?

Discussion of Problem 1115. Ships