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.

Answer rating: 100% (QA)

1 Let us define some of the terms will be used for the algorithm Let X is set of problems that can b... View the full answer