Question: 8. What is the time complexity of the following dynamic programming implementation of the Knapsack problem with n items and a maximum weight of W?<div class="hk1_style-wrap4"><div class="hk1_style-wrap3"><div class="hk1_style-wrap2"><div class="hk1_style-wrap"><div class="hk1_style"><div class="c"><pre class="de1"><span class="co2">#include&lt;stdio.h&gt;</span> <span class="kw4">int</span> find_max<span class="br0">(</span><span class="kw4">int</span> a<span class="sy0">,</span> <span class="kw4">int</span> b<span class="br0">)</span> <span class="br0">{</span> <span class="kw1">if</span><span class="br0">(</span>a <span class="sy0">&gt;</span> b<span class="br0">)</span> <span class="kw1">return</span> a<span class="sy0">;</span> <span class="kw1">return</span> b<span class="sy0">;</span> <span class="br0">}</span> <span class="kw4">int</span> knapsack<span class="br0">(</span><span class="kw4">int</span> W<span class="sy0">,</span> <span class="kw4">int</span> <span class="sy0">*</span>wt<span class="sy0">,</span> <span class="kw4">int</span> <span class="sy0">*</span>val<span class="sy0">,</span><span class="kw4">int</span> n<span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> ans<span class="br0">[</span>n <span class="sy0">+</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>W <span class="sy0">+</span> <span class="nu0">1</span><span class="br0">]</span><span class="sy0">;</span> <span class="kw4">int</span> itm<span class="sy0">,</span>w<span class="sy0">;</span> <span class="kw1">for</span><span class="br0">(</span>itm <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> itm <span class="sy0">&lt;=</span> n<span class="sy0">;</span> itm<span class="sy0">++</span><span class="br0">)</span> ans<span class="br0">[</span>itm<span class="br0">]</span><span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span> <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> <span class="kw1">for</span><span class="br0">(</span>w <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span>w <span class="sy0">&lt;=</span> W<span class="sy0">;</span> w<span class="sy0">++</span><span class="br0">)</span> ans<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span><span class="br0">[</span>w<span class="br0">]</span> <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> <span class="kw1">for</span><span class="br0">(</span>itm <span class="sy0">=</span> <span class="nu0">1</span><span class="sy0">;</span> itm <span class="sy0">&lt;=</span> n<span class="sy0">;</span> itm<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw1">for</span><span class="br0">(</span>w <span class="sy0">=</span> <span class="nu0">1</span><span class="sy0">;</span> w <span class="sy0">&lt;=</span> W<span class="sy0">;</span> w<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw1">if</span><span class="br0">(</span>wt<span class="br0">[</span>itm <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span> <span class="sy0">&lt;=</span> w<span class="br0">)</span> ans<span class="br0">[</span>itm<span class="br0">]</span><span class="br0">[</span>w<span class="br0">]</span> <span class="sy0">=</span> find_max<span class="br0">(</span>ans<span class="br0">[</span>itm <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>w<span class="sy0">-</span>wt<span class="br0">[</span>itm <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">]</span><span class="sy0">+</span>val<span class="br0">[</span>itm <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span><span class="sy0">,</span> ans<span class="br0">[</span>itm <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>w<span class="br0">]</span><span class="br0">)</span><span class="sy0">;</span> <span class="kw1">else</span> ans<span class="br0">[</span>itm<span class="br0">]</span><span class="br0">[</span>w<span class="br0">]</span> <span class="sy0">=</span> ans<span class="br0">[</span>itm <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>w<span class="br0">]</span><span class="sy0">;</span> <span class="br0">}</span> <span class="br0">}</span> <span class="kw1">return</span> ans<span class="br0">[</span>n<span class="br0">]</span><span class="br0">[</span>W<span class="br0">]</span><span class="sy0">;</span> <span class="br0">}</span> <span class="kw4">int</span> main<span class="br0">(</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> w<span class="br0">[</span><span class="br0">]</span> <span class="sy0">=</span> <span class="br0">{</span><span class="nu0">10</span><span class="sy0">,</span><span class="nu0">20</span><span class="sy0">,</span><span class="nu0">30</span><span class="br0">}</span><span class="sy0">,</span> v<span class="br0">[</span><span class="br0">]</span> <span class="sy0">=</span> <span class="br0">{</span><span class="nu0">60</span><span class="sy0">,</span> <span class="nu0">100</span><span class="sy0">,</span> <span class="nu0">120</span><span class="br0">}</span><span class="sy0">,</span> W <span class="sy0">=</span> <span class="nu0">50</span><span class="sy0">;</span> <span class="kw4">int</span> ans <span class="sy0">=</span> knapsack<span class="br0">(</span>W<span class="sy0">,</span> w<span class="sy0">,</span> v<span class="sy0">,</span> <span class="nu0">3</span><span class="br0">)</span><span class="sy0">;</span> <span class="kw3">printf</span><span class="br0">(</span><span class="st0">"%d"</span><span class="sy0">,</span>ans<span class="br0">)</span><span class="sy0">;</span> <span class="kw1">return</span> <span class="nu0">0</span><span class="sy0">;</span> <span class="br0">}</span></pre></div></div></div></div></div></div>
Options:
O(n)
O(n + w)
O(nW)
O(n2)
Answer: A