Question $3(20$ marks$)$

There are $n$ items and a "knapsack". Each item i has weight $w_i>0$ and has value $v_{i}0.$ Knapsack has capacity of $W_{?}.$ The goal is to fill knapsack so as to maximize total value. Please adopt dynamic programming to handle the following instance of the knapsack problem. For example, weight capacity $W=5kg.$ Item $1$ has weight $1$ kg and has value $$10.$ Item $2$ has weight $1$ kg and has value $$11.$ Item $3$ has weight $2$ kg and has value $$13.$ Item $4$ has weight $3$ kg and has value $$18.$

$($a$)$ Show the recursion property and your idea. $($Hint: use $V(i,j)$ to represent the optimal solution of items subset $\{1,$dots,$i\}$ with capacity $j.)[10$ marks$]$

$($b$)$ Fill in the table and show how to get the optimal solution, i$.$e$..$ The empty table is shown as follows. $[10$ marks$].$

Page $1$ of $2$

CONFIDENTIAL

$202204/$CST$207/$A

$\backslash$table$[[,j=0,j=1,j=2,j=3,j=4,j=5$