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 elementof 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 elementof P? Justify your