D ...

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

In the knapsack problem we are given a set of n items, where each item i is specified by a size si and a value vi. We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

We are trying to use Dynamic programming paradigm to reduce the time complexity for the solution. The algorithm follows

Value(n,S) { if (n == 0) return 0; if (arr[n][S] != unknown) return arr[n][S]; if (s_n > S) result = Value(n-1,S); else result = max{v_n + Value(n-1, S-s_n), Value(n-1, S)}; XXXX return result; }

What statement can go in the place of XXXX to make algorithm complete?

(A) No Statement is needed. It is already complete algorithm.

(B) arr[S][n]= result;

(C) arr[n][n]= result;

(D) arr[n][S] = result;

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 21
- Job Queries 61
- Projects 13

39,657 questions

46,732 answers

140,417 comments

58,136 users