A farmer wants to sell his farm products in the city. He has a knapsack with the capacity of “N” kgs weight, and he has products with more than ‘N’ kgs weight. He wants to fill his backpack in such a way that he gets more money after selling the products in the knapsack. Here 0/1(zero or one) means either pick the product or ignore. We can’t cut the product.

For example a knapsack with “8” Kgs capacity and products like {2,5}, {5,13}, {3,4}, {1,2}, {6,14} which are {weight, costs} respectively. Let’s see below picture to get better understanding.

Here the capacity of the Knapsack and weight, costs of products are given as inputs to the problem.

```
// Inputs
8 // is capacity of the Knapsack
5 // Number of products
2, 1, 3, 5, 6 // Weights of respective products
5, 2, 4, 13, 14 // Costs of the respective products
// Output ( we need to get the maximum price that we can make using knapsack.
20 // We can get at max 20 units by using the 8kg knapsack.
```

We can solve this problem using below two approaches.

- Recursion.
- Dynamic Programming.

#### Recursion solution

This problem is like a coin change problem where we either can pick the coin or ignore it, 0/1 knapsack mean either we choose a product or ignore it.

We can make a recursive formula for this problem, there are two choices we can have with a product, either we can pick it or ignore it. Finally, we need to maximize the cost between both. The recursion formula is like

```
F({items}, capacity, currentItem) =
maximum { (current Item value +
F({items}, capacity - weight of current item, currentItem+1)),
F({items}, capacity, currentItem+1) }
Maximum value we can make by picking the product or ignoring it.
```

Code for this recursive approach is as follows

```
int maxCostKnapsackUsingRec(vector<Item> items, int knapsackWeight, int currItem)
{
if (knapsackWeight == 0 ||
currItem == items.size())
{
return 0;
}
Item item = items.at(currItem);
if (item.weight > knapsackWeight)
{
return maxCostKnapsackUsingRec(items, knapsackWeight, currItem + 1);
}
int maxCostIfPick = item.cost +
maxCostKnapsackUsingRec(items, knapsackWeight - item.weight, currItem + 1);
int maxCostIfNotPick =
maxCostKnapsackUsingRec(items, knapsackWeight, currItem + 1);
return max(maxCostIfNotPick, maxCostIfPick);
}
```

This recursive approach runs with an exponential complexity, which is . To overcome this runtime complexity drawback, we can come up with a solution using Dynamic Programming. Let’s see how that will work.

#### Dynamic Programming

We need to memorize the solution at each part of the weights. Let’s see below the dynamic memorization for our problem.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |

(2,5) | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |

(5,13) | 0 | 0 | 5 | 5 | 5 | 13 | 13 | 18 | 18 |

(3,4) | 0 | 0 | 5 | 5 | 5 | 13 | 13 | 18 | 18 |

(1,2) | 0 | 2 | 5 | 7 | 7 | 13 | 15 | 18 | 20 |

(6,14) | 0 | 2 | 5 | 7 | 7 | 13 | 15 | 18 | 20 |

Let’s see the formula and code for the dynamic programming approach solution.

```
dp[i][j] = dp[i-1][j] // if weight of product is < current weight.
= max{ dp[i-1][j],
dp[i-1][j-weight[i]] + cost of j item } // Otherwise.
```

```
int maxCostKnapsackUsingDP(vector<Item> items, int knapsack)
{
int size = items.size();
int dp[size][knapsack + 1];
for (int i = 0; i < size; i++)
{
for (int j = 0; j <= knapsack; j++)
{
if (j == 0)
{
dp[i][j] = 0;
continue;
}
Item item = items.at(i);
if (i == 0)
{
dp[i][j] = (j < item.weight) ? 0 : item.cost;
}
else
{
if (j < item.weight)
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j],
dp[i - 1][j - item.weight] + item.cost);
}
}
cout << dp[i][j] << " ";
}
cout << endl;
}
return dp[size - 1][knapsack];
}
```

Complexity of this solution is . Complete code with main function is as showing below.

```
// Output
0/1 Knapsack problem using Recursion:
20
0/1 Knapsack problem using Dynamic Programming:
20
```

It is all about the 0/1 Knapsack problem with both recursive and dynamic programming approaches. If you know any better solution, please let our readers know by commenting here below. Happy Learning!.