Define how Knapsack Problem is Solved by dynamic programming.

Consider n=3(w, w, w₁)=(2, 3, 3), (P,, P₂, P₂)=(1,2,4) and 6. Find optimal solution.

n = 3 (number of items)

w₁ = 2, w₂ = 3, w₃ = 3 (weights of the items)

P₁ = 1, P₂ = 2, P₃ = 4 (values of the items)

W = 6 (maximum weight capacity)

## Step 01:

Create table.

```
+---+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | | | | | | |
| 2 | 0 | | | | | | |
| 3 | 0 | | | | | | |
+---+---+---+---+---+---+---+---+
```

## Step 02:

Fill in the table:

For item 1 (w₁ = 2, P₁ = 1):

```
+---+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | | | | | | |
| 3 | 0 | | | | | | |
+---+---+---+---+---+---+---+---+
```

## Step 03:

For item 2

(w₂ = 3, P₂ = 2):

```
+---+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 2 | 2 | 2 | 2 |
| 3 | 0 | | | | | | |
+---+---+---+---+---+---+---+---+
```

## Step 04:

For item 3

(w₃ = 3, P₃ = 4):

```
+---+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 2 | 2 | 2 | 2 |
| 3 | 0 | 0 | 1 | 4 | 4 | 4 | 6 |
+---+---+---+---+---+---+---+---+
```

The optimal solution is the value in the bottom-right corner of the table, which is dp[3][6] = 6. Therefore, the maximum value that can be achieved without exceeding the weight capacity of 6 is 6.