in Algorithms recategorized by
367 views
1 vote
1 vote

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
in Algorithms recategorized by
367 views

1 comment

As per the dynamic Programming recurrence relation, the solution to $i^{th}$ subproblem only depends on the solution to $(i-1)^{th}$ subproblem. 

For example, in matrix multiplication the result does not depend only on the $(i-1)^{th}$ subproblem.

It requires us to find a combination even from results older than that.

So, shouldn't this be a False statement.

  

0
0

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.

1 comment

As per the dynamic Programming recurrence relation, the solution to $i^{th}$ subproblem only depends on the solution to $(i-1)^{th}$ subproblem. 

For example, in matrix multiplication the result does not depend only on the $(i-1)^{th}$ subproblem.

It requires us to find a combination even from results older than that.

So, shouldn't this be a False statement.

  

1
1
Answer:

Related questions