Question 1. (15 marks) a. (5 marks) Consider the 0-1 knapsack problem for items

Question

Question 1. (15 marks) a. (5 marks) Consider the 0-1 knapsack problem for items 1 whose values are 4,3, 6, 5, 7 and whose weights are 2,2, 3, 4, 5. Assume the knapsack capacity is 10. Apply the knapsack algorithm in the lecture notes to the problem by filling the array A5, 10], and apply the Print-Opt-Knapsack procedure to show which items are in your optimal solution. b. (5 marks) Matrices A, B, C, D, E have respective dimensions 1 x 5, 5 x 2, 2 x 6, 6 x 1, 1 x 4. What is the minimum number of scalar multiplications needed to compute A x Bx C x D x E? Give the parenthesization of matrices that yields this number. Show how you arrived at your answer c. (5 marks) se Stressen's algorithm to compute the following matrix product. Show your work, but for multiplications involving only 2 x 2 matrices you can just give the result. 8 2 31 3 2 44 81 7 4 5 5 1 1 6 3 2 3 5 5 2 2 6 3 7 3 6 3 1 5 4 1 4

Explanation / Answer

a.)

A[5, 10]

first we will calculate effective value of the profit, see the table given below:

now since the capacity is 10, we need to fill valuable items in knapsack

so in the first call to kanpsack(5, 10) item 5 will be entered into the knapsack, now 10-5= 5 (only 5 weight is remaining to fill) and so far the profit is 35

so in the second call kanpsack(4, 5) item 4 will be entered into the knapsack with weight 4, now remaining weight= >5-4= 1, and the profit is 35+24=59

now at third call of knapsack(3, 1) there is no item with weight 1 to be filled to the algorithm will terminate here.

and profit will be 59.

b)

To minimize the minimum number of multiplication first we will multiply 2X6 and 6X1, here number of multiplication will be
2*6*1= 12, and the resultant matrix will be 2X1

then, then we will multiply 1X5 and 5X2, here number of multiplication will be 1*5*2= 10, and the resultant matrix will be 1X2
Total multiplications so far=> 12+10= 22

Then we will multiply both of our resultant matrix, here number of multiplication will be 1*2*1= 2

So far total number of multiplications= 22+2= 24, resultant matrix will be 1X1

Now, at last we will multiply 1X1 and 1X4, number of multiplications= 1*1*4= 4

So total number of multiplications will be 24+4= 28, and the dimension of resultant matrix will be 1X4

Object 1 2 3 4 5 Value 4 3 5 6 7 Weight 2 2 3 4 5 Profit 8 6 15 24 35

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.