Question: Explain Knapsack Algorithm
0

Knapsack Algorithm

• It is based on public key encryption algorithms and knapsack

• Given a note of items, each with different weights, it is possible to put some of the items in a bag in such a way that it should not be greater than the weight of the knapsack

• If $V_1, V_2, V_3…..V_4$ are the values, we have to find b? Such that

$\hspace{1.5cm}$$\hspace{1.5cm}S = b_1v_1 + b_2v_2 + b_3v_3 ……..+ b_nv_n$ When S is the sum. • Each bit can be 0 or 1 • ‘1’ indicates that the item is in the knapsack and a ‘0’ indicates it is not • A block of plaintext equal in length to the number of items in the pile would select the items in the knapsack. The ciphertext is the resulting sum . e.g : 1,7,8,12,14 and 20 are the knapsack then the plaintext and the resulting ciphertext is as given below $\hspace{1.5cm}$

it cns • 306 views