Answer to Question #271983 in Algorithms for Anu

Question

(i) Formulate the Knapsack problem and write the pseudo code for solving a fractional

Knapsack problem. Also calculate its time complexity.

(ii) Find an optimal solution for the knapsack instance n (number of objects) =7 and

W ( totalweight) =15. Profits and weights of each object are shown below:

(p1, p2………..p7) = (10, 5, 15, 7, 6, 18, 3)

(w1, w2………w7) = (2, 3, 5, 7, 6, 4, 1)

Show all the steps.

Answer 1

i)

The most common problem being solved is the 0-1 knapsack problem, which restricts the number x_i of copies of each kind of item to zero or one. Given a set of n items numbered from 1 up to  n, each with a weight w_i and a value v_i, along with a maximum weight capacity W