P3 (10 points) (UNBOUNDED Knapsack) Given an unlimited number of the items below
ID: 3605614 • Letter: P
Question
P3 (10 points) (UNBOUNDED Knapsack) Given an unlimited number of the items below: Item Weight: 4 Value: 10 12 36 a) (7 points) Fill out the solution array, sol, using bottom-up dynamic programming. Follow the style we did in class: for each work-out box (in rows for items A,B,C,D) show the remaining weight and the optimal value obtained by using that item. (You do not have to show the actual calculation to get the remaining weight. E.g. in the table below row A, problem size 5, shows the remaining weight, 1, and optimal value using item A, 10.) Fill-out all the table (starting from 0) 0 23 4 5 678 9 10 12 Sol Picked b) (3 points) Use the table above to recover the items that achieve the optimal value for weight 12.Explanation / Answer
Part-A
Item:
A
B
C
D
Weight:
4
6
10
12
Value:
10
21
33
36
0
1
2
3
4
5
6
7
8
9
10
11
12
Sol:
0
0
0
0
10
10
21
21
21
21
33
33
42
Picked
none
none
none
none
A
A
B
B
B
B
C
C
B
A
0
0
1
0
2
0
3
0
0
10
1
10
2
10
3
10
0
20
1
20
2
20
3
20
0
30
B
0
0
1
0
2
0
3
0
0
10
1
10
0
21
1
21
2
21
3
21
0
31
1
31
0
42
C
0
0
1
0
2
0
3
0
0
10
1
10
0
21
1
21
2
21
3
21
0
33
1
33
0
42
D
0
0
1
0
2
0
3
0
0
10
1
10
0
21
1
21
2
21
3
21
0
33
1
33
0
42
Part-B:
As shown in above table on 12 we are picking B => first item picked is B
now we have left with 12-weight of B = 12-6 = 6
and again on 6, we are picking B.
now left weight = 6 - weight of B = 6-6 = 0
So for 12, we are picking 2 B.
Item:
A
B
C
D
Weight:
4
6
10
12
Value:
10
21
33
36
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.