NP-hard

Suppose there is just one boat and the utility for every ppl getting on that boat is 1. The problem then becomes finding the maximum number of ppl that can get on the boat simultaneously, which is the maximum independent set problem and hence NP-hard.

The two extensions you mentioned are also NP-hard.

My suggestion is looking for heuristics...

所有跟帖： 

• 谢谢，不过。。。 -说了就走- ♂ (305 bytes) () 09/13/2008 postreply 21:31:27