An instance of the knapsack problem is given by a knapsack w

An instance of the knapsack problem is given by a knapsack with integer capacity C, and n items, where item i has integer weight wi and integer value vi . What is the size of the encoding of this instance?

Solution

val= maximum(n-1 items , W weight (excluding nth item)

value of nth term

Value of nth item + val - weight of the nth item (including nth item)..

now n = sizeof(val)/sizeof(val[0])