Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Knapsack Problem Solved by dynamic programming

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.