367 views

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

### 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.

$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 vote