The Knapsack Problem ( KP ) gives you a target integer t and an array data with
Question:
The Knapsack Problem ( KP ) gives you a target integer t and an array data with n positive integers, and it returns the subset of data with a sum as close
as possible to t without going over.
The Knapsack Size Problem ( KSP ) gives you a target integer t and an array data with n positive integers, and it returns the largest integer less than t that
some subset of data sums up to.
The Full Knapsack Problem ( FKP ) gives you a target integer t and an array data with n positive integers, and it returns true if there is a subset of data
that sums to exactly t and false otherwise.
1. Prove that FKP ∈ NP by giving pseudocode for a polynomial-time verification algorithm for FKP .
2. What kind of reduction do you need between FKP and KSP in order to prove that KSP ∈ P if FKP ∈ P ? Justify your answer.
Elementary Linear Algebra with Applications
ISBN: 978-0132296540
9th edition
Authors: Bernard Kolman, David Hill