Question No.1 You have to give the dynamic programming tables (m tablefor comput
ID: 3615988 • Letter: Q
Question
Question No.1
You have to give the dynamic programming tables (m tablefor computing best optimal
value and k table having track of matrices) for the belowmatrices, you also need to show
the optimal final matrix multiplication tree usingk table.
A1 . A2 . A3 . A4 . A5 . A6
(2x3) (3x7) (7x5) (5x6) (6x4) (4x3)
0/1Knapsack1 Problem:
Knapsack Problem is that,
· Wehave to fill a bag that can carry maximum weightW
· Wehave to fill the bag with different items each having acertain weight and
value
· Wewant to fill the bag with these items such that total value ofitems present in
bag is maximum and total weight of items doesn’tincrease maximum 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.
Already solved your thisquestion. You can chem it . /computer-science-answers-5-738123-cpi0.aspx Please Rate both answersWeight 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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.