An instance of the $0-1$ Knapsack decision problem is a triple $(I,c,p),$ where $I=\{x_1,$dots,$x_n\}$

is a set of $n$ items, $c0$ is the knapsack capacity, and $p0$ is the desired profit. Moreover,

associated with each item $x_i$inI is a weight $w_{i}0$ and profit $p_{i}0.$ The problem is to decide

if there is a subset of items from I for which i$)$ the sum their weights does not exceed $c,$ and

ii$)$ the sum of their profits is equal to $p.$ For example, the table below shows the items from a

positive instance of $0-1$ Knapsack for which $c=10$ and $p=140.$ The instance is positive since

$\{x_2,x_4,x_5\}subeI$ have a total weight equal to $5+1+4c$ and a total profit of $60+30+50=p.$

The goal of this exercise is to establish that $0-1$ Knapsack is a member of complexity class NP$.$

$($a$)$ For given instance $(I,c,p)$ of $0-1$ Knapsack describe a certificate in relation to $(I,c,p).$

$(5$ points$)$

$($b$)$ Provide a semi$-$formal verifier algorithm that takes as input i$)$ an instance $($ I,$c,p),$ and

ii$)$ a certificate for $(I,c,p)$ as defined in part a$,$ and decides if the certificate is valid for

points

please do not copy paste from the chatgpt or any other ai tool