Question No.1 You have to give the dynamic programming tables (m table forcomput
ID: 3615973 • Letter: Q
Question
Question No.1
You have to give the dynamic programming tables (m table forcomputing best optimal
value and k table having track of matrices) for the belowmatrices, you also need to show
the optimal final matrix multiplication tree using ktable.
A1 . A2 . A3 . A4 . A5 . A6
(2x3) (3x7) (7x5) (5x6) (6x4) (4x3)
0/1Knapsack1 Problem:
Knapsack Problem is that,
· We have to fill a bag that can carrymaximum weight W
· We have to fill the bag withdifferent items each having a certain weightand
value
· We want to fill the bag with theseitems such that total value of items present in
bag is maximum and total weight of items doesn’t increasemaximum weight that
bag can carry(W).
Explanation / Answer
Weight Limit (j)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
w1=4, v1=3
0
0
0
3
3
3
3
3
3
3
3
3
3
3
3
w2=2, v2=7
0
7
7
7
7
10
10
10
10
10
10
10
10
10
10
w3=6, v3=2
0
7
7
7
7
10
10
10
10
10
10
12
12
12
12
w4=8, v4=6
0
7
7
7
7
10
10
10
10
13
13
13
13
16
16
w5=2, v5=4
0
7
7
11
11
11
11
11
11
13
13
17
17
17
17
w6=8, v6=5
0
7
7
11
11
11
11
14
14
14
14
17
17
17
17
w7=3, v7=1
0
7
7
11
11
11
12
14
14
14
15
17
17
17
18
He take item w2(value=7), w8(value=6), w2(value 4), w3(value=1),then he gets total 18. which is maximum value and weight is 15Kg.
Weight Limit (j)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
w1=4, v1=3
0
0
0
3
3
3
3
3
3
3
3
3
3
3
3
w2=2, v2=7
0
7
7
7
7
10
10
10
10
10
10
10
10
10
10
w3=6, v3=2
0
7
7
7
7
10
10
10
10
10
10
12
12
12
12
w4=8, v4=6
0
7
7
7
7
10
10
10
10
13
13
13
13
16
16
w5=2, v5=4
0
7
7
11
11
11
11
11
11
13
13
17
17
17
17
w6=8, v6=5
0
7
7
11
11
11
11
14
14
14
14
17
17
17
17
w7=3, v7=1
0
7
7
11
11
11
12
14
14
14
15
17
17
17
18
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.