Knapsack Scheme (Merkel and Hellman, 1978) Given X=(XI, x2, . Xn)and a integer s Finding B=(b,b,,, bn)where b ;=0or such that s=bx=<X,B>=∑bx1 NP-Complete in generalKnapsack Scheme (Merkel and Hellman, 1978) • Given X = (x1 , x2 ,…, xn ) and a integer s • Finding B = (b1 , b2 ,…, bn ) where bi = 0 or 1 such that s = bi xi= < X, B> =  bi xi • NP-Complete in general