91Ó°ÊÓ

Let the sub problem be $\mathrm{D}\left(\mathrm{n},\mathrm{V}\right)$.

A sub-problem$D\left(v−x_i\right)$ is made at each step, from unused denomination.

The possible cases are:

• $D\left(n−1,V−x_n\right)=\text{TRUE}$implies that coin of denomination $x{}_n$ is used to make value $V$, so $V−x_n$can be made using $n−1$number of coins. So, $D\left(n,V\right)$will also be true.
• $D\left(n−1,V\right)=\text{TRUE}$ implies that a coin with denomination $x{}_n$is not used to make value V and V can be made from$n−1$ coin, so$D\left(n,V\right)$ is true.
• If both above discussed cases are not true that means,$D\left(n,V\right)$ then V cannot be obtained from n coins.

Based on above conditions, the recurrence relation is as follows:

$D\left(n,V\right)=\left\{\begin{array}{c}1;ED\left(n−1,V−x_n\right)ORD\left(n−1,V\right)\\ 0;\text{otherwise}\end{array}\right.$

The algorithm is given as follows:

Consider an array of coins

$\begin{array}{l}D\left(i,0\right)=\text{True}\\ \text{for}\left(i=0\text{â€Ôò´Ç n}\right)\\ \text{ â¶Ä„â¶Ä„}D\left(i,0\right)=\text{True}\\ \text{for}\left(i=1\text{â€Ôò´Ç n}\right)\\ \text{ â¶Ä„â¶Ä„for}\left(j=1\text{â€Ôò´Ç V}\right)\end{array}$

$\begin{array}{l}\text{ â¶Ä„â¶Ä„ â¶Ä„â¶Ä„if}\left(\text{x}\left[i−1\right]≤j\right)\\ \text{ â¶Ä„â¶Ä„ â¶Ä„â¶Ä„ â¶Ä„â¶Ä„}D\left(i,j\right)=\left(D\left(i−1,j−x\left[i−1\right]\right)\text{°¿¸é }D\left(i−1,j\right)\right)\\ \text{ â¶Ä„â¶Ä„ â¶Ä„â¶Ä„else}\\ \text{ â¶Ä„â¶Ä„ â¶Ä„â¶Ä„ â¶Ä„â¶Ä„}D\left(i,j\right)=D\left(i−1,j\right)\\ \text{°ù±ð³Ù³Ü°ù²Ô }D\left(n,V\right)\end{array}$

The first loop runs for n times. There two nested loops takes nV times. Since, $n<<nV$

Thus, the runtime of the algorithm is $O\left(nV\right)$.