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.