Question

What is the solution to the knapsack problem?

(a) many-to-many mapping

(b) one-to-many mapping

(c) many-to-one mapping

(d) one-to-one mapping

This question was posed to me at a job interview.

This question is from Compilers topic in chapter Implementing Embedded System: Hardware/Software Codesign of Embedded Systems

Answer 1

Right choice is (d) one-to-one mapping

The best I can explain: The knapsack problem is associated with the size constraints, that is the size of the scratch pad memories. This problem can be solved by one-to-one mapping which was presented in an integer programming model by Steinke et al.