1.

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) 010010I 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»

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.



Discussion

No Comment Found

Related InterviewSolutions