Question

Consider knapsack that weighs 23 that has been made from the weights of the superincreasing series {1, 2, 4, 9, 20, and 38}. Find the ‘n’.

(a) 011111

(b) 010011

(c) 010111

(d) 010010

I had been asked this question in semester exam.

This intriguing question originated from Knapsack/ Merkle in portion Public Key Cryptography and RSA of Cryptograph & Network Security

Answer 1

Correct option is (b) 010011

Easy explanation: v0=1, v1=2, v2=4, v3=9, v4=20, v5=38

  K=6, V=23

Starting from largest number:

v5 > V then    ϵ_5=0

v4 < V then V = V – v4 = 23 – 20 = 3 ϵ_4=1

v3 > V then     ϵ_3=0

v2> V then     ϵ_2=0

v1 < V then V = V – v1= 3 – 2 = 1 ϵ_1=1

v0 =1 then V = V – v0= 1 – 1 = 0  ϵ_0=1

   n= ϵ_5 ϵ_4 ϵ_3 ϵ_2 ϵ_1 ϵ_0 = 010011.