March 3rd, 2004, 05:22 AM
|
 |
Major General
|
|
Join Date: Oct 2003
Location: Crystal Tokyo
Posts: 2,453
Thanks: 0
Thanked 0 Times in 0 Posts
|
|
Re: Better, Simpler Programming Contest
Quote:
Originally posted by Leif_-:
quote:
Originally posted by mlepinski:
Which raises the question: Is the problem that Saber Cherry posed NP-Complete?
|
Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete?
Hmmm.
It looks like a multidimensional variant of the unbounded knapsack problem. Adding the combined arms bonus would change that, though. |