recategorized by
565 views
1 votes
1 votes

Consider the Knapsack Problem: Given a set of n items, each with a weight $w_i$ and the value $v_i$ determine a subset of items to include in a collection so that the total weight is $\leq W$ which is a given limit and the total value is as large as possible. Consider the following statements in a situation such that we want to solve this problem using the Dynamic Programming paradigm.

  1. As per the dynamic Programming recurrence relation, the solution to $i^{th}$ subproblem only depends on the solution to $(i-1)^{th}$ subproblem.
  2. The number of distinct subproblems is $O(nW)$.

Which of the above statements is/are correct?

  1. I only
  2. II only
  3. Both I and II
  4. None of these
recategorized by

1 Answer

0 votes
0 votes
$f_i(w) = $ maximum value obtainable with $i$ objects and a knapsack capacity $W$.
$f_i(w) = \text{max}(f){i-1} (w) , \: v_i +f_{i-1}(w-w_i))$
$f_i$ depends on $f_{i-1}$ subproblem only.
So, statement I is correct.
For $f_i(x)$
$i \in \{0, 1, 2, \dots , n\}$
$x \in \{0, 1, 2, \dots, n \}$
Number of distinct subproblems $=O(nW)$
So, statement II is correct.
Answer:

Related questions

1 votes
1 votes
1 answer
4
Applied Course asked Jan 16, 2019
502 views
Suppose a radix sort was done on the following set of numbers, in binary i.e,$[11, 10, 3, 14, 12, 2, 8, 15, 2]$. How many passes of counting sort would be performed _____...