Question

A thief rubbing a safe finds it filled with N types of items of varying size and value, but has only a small knapsack of capacity M to use to carry the goods. The knapsack problem is to find the combination of items which the thief should choose for the knapsack in order to maximize the total value of the stolen items.

Answer 1

Pseudo code:-

Algorithm:-

1).First find the ratios of value / size for all N items and store it in some another array.

2).Now,after that sort the array of ratios in descending order obtained in step 1). using any sorting algorithm say heap sort using minheaps.

3).initialise totalValue = 0, i = 0

4).Check for i^th entry in array obtained in step 2) if size of ith item exceeds the available size in knapsack or not.

5).If it doesn't exceeds then new M = M - size of ith item and totalValue = valueofithItem + totalValue to which that ratio belongs to.

6).do step 3 to 5 for all items.

7).If in step 5). Size exceeds then set M = 0 and totalValue = totalValue + Value of ith item to which (ratio belongs to / size of ith item )*M

And exit immediately.

Pseudo code:-

Knapsack(a,N,M)// a is input array,N is number of items and M is knapsack capacity.

{

for i = 1 to N

b[i] = value(i) / size(i)

totalValue = 0

HeapSort(b)// sort array b.

While(M>0 and j != N-1)

{

if(size(j)

{

totalValue = value(j) + totalValue

M= M - size(j)

}

else

{

totalValue = totalValue +( value(j)/ size(j))*M

M = 0

}

}

}

TIME COMPLEXITY

= O(N) + O(NlogN) + O(N)

= O(NlogN)