0
$\begingroup$

(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}

(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, 3, 9, 81 } (essentially powers of 3)

(iii) Is there any limitations on the relationship between the numbers of the set and the size of the knapsack?

(iv) If I were to make my own knapsack problem what strict criteria must I follow? For instance, is a knapsack of 3, and the set {1, 5, 6, 2} a legitimate knapsack problem? Meaning this example has the complexity class NP-Complete?

  • 0
    I expected as much. I apologise.2011-08-08

1 Answers 1

2

You tell us! :-) How are we supposed to know what problem you're dealing with? If you're talking about what's usually called the knapsack problem, you can easily find the answers to your questions at Wikipedia; there's no mention of coprimality, similarity or any other restrictions on the numbers or their number there. Regarding your last question, complexity is a property of a problem class, not of problem instances.

  • 0
    @C'est Moi: You're welcome.2011-08-08