Knapsack Algorithm

• It is based on public-key encryption algorithms and knapsack

• The problem statement is, given an 'n' number of items, each with different weights,we have to put items in a bag with certain capacity in such a way that the items put in the bag should not weigh greater than the weight of the knapsack that means that the total weight of the items to be put in the bag should be equal to the weight of the knapsack.

• If $V_1, V_2, V_3…..V_n$ are the values of the items and S is the sum of the weight of knapsack, we have to find $b_i$?

$\hspace{1.5cm}$$\hspace{1.5cm}S = b_1v_1 + b_2v_2 + b_3v_3 ……..+ b_nv_n$ - Each bit $b_i$ can be 0 or 1

• ‘1’ indicates that the item is taken 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. .

• For example : 1,7,8,12,14 and 20 is the knapsack then the plaintext and the resulting ciphertext is as given below