Skip to main content
Post Closed as "not a real question" by Will Jagy, user9072, David Roberts, Andreas Blass, Gerry Myerson
Edited tags
Link
David Roberts
  • 35.5k
  • 11
  • 124
  • 349
gramm'err
Source Link

(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 For instance, is a knapsack of 3, and athe set of {1, 5, 6, 2} a legitimate knapsack problem? Meaning this example has a complexity class NP-Complete? I understand the concepts of weakly NP-Complete and pseudo-polynomial time...

(v) If one shows a problem to be a knapsack problem, and solves the problem with a psuedo-polynomial algorithm, is it possible that the same algorithm could not be used to solve all examples of knapsacks with limited sets of relatively small integers? If so, would this algorithm still be considered a solution to the Knapsack Problem or simply a solution to this unique instance of the Knapsack Problem?

(vI) Lastly, how important is it for the 'boxes' to have values and weights? It seems to me the subset sum, which is NP-Complete by reduction from the Knapsack Problem, only has weights and lacks the value variable? (As depicted in the wikipedia.org entry associated image)

I have read the wikipedia.org entry extensively as well as some arXiv entries on the subject and excerpts of books on Google Books along with other random online resources, but I was still left with these questions... Thank you

(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 a set of {1, 5, 6, 2} a legitimate knapsack problem? Meaning this example has a complexity class NP-Complete? I understand the concepts of weakly NP-Complete and pseudo-polynomial time...

(v) If one shows a problem to be a knapsack problem, and solves the problem with a psuedo-polynomial algorithm, is it possible that the same algorithm could not be used to solve all examples of knapsacks with limited sets of relatively small integers? If so, would this algorithm still be considered a solution to the Knapsack Problem or simply a solution to this unique instance of the Knapsack Problem?

(vI) Lastly, how important is it for the 'boxes' to have values and weights? It seems to me the subset sum, which is NP-Complete by reduction from the Knapsack Problem, only has weights and lacks the value variable? (As depicted in the wikipedia.org entry associated image)

I have read the wikipedia.org entry extensively as well as some arXiv entries on the subject and excerpts of books on Google Books along with other random online resources, but I was still left with these questions... Thank you

(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 a complexity class NP-Complete? I understand the concepts of weakly NP-Complete and pseudo-polynomial time...

(v) If one shows a problem to be a knapsack problem, and solves the problem with a psuedo-polynomial algorithm, is it possible that the same algorithm could not be used to solve all examples of knapsacks with limited sets of relatively small integers? If so, would this algorithm still be considered a solution to the Knapsack Problem or simply a solution to this unique instance of the Knapsack Problem?

(vI) Lastly, how important is it for the 'boxes' to have values and weights? It seems to me the subset sum, which is NP-Complete by reduction from the Knapsack Problem, only has weights and lacks the value variable? (As depicted in the wikipedia.org entry associated image)

I have read the wikipedia.org entry extensively as well as some arXiv entries on the subject and excerpts of books on Google Books along with other random online resources, but I was still left with these questions... Thank you

Source Link

Knapsack Problem Specifics

(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 a set of {1, 5, 6, 2} a legitimate knapsack problem? Meaning this example has a complexity class NP-Complete? I understand the concepts of weakly NP-Complete and pseudo-polynomial time...

(v) If one shows a problem to be a knapsack problem, and solves the problem with a psuedo-polynomial algorithm, is it possible that the same algorithm could not be used to solve all examples of knapsacks with limited sets of relatively small integers? If so, would this algorithm still be considered a solution to the Knapsack Problem or simply a solution to this unique instance of the Knapsack Problem?

(vI) Lastly, how important is it for the 'boxes' to have values and weights? It seems to me the subset sum, which is NP-Complete by reduction from the Knapsack Problem, only has weights and lacks the value variable? (As depicted in the wikipedia.org entry associated image)

I have read the wikipedia.org entry extensively as well as some arXiv entries on the subject and excerpts of books on Google Books along with other random online resources, but I was still left with these questions... Thank you