# Write a program to solve the 0-1 Knapsack problem using the recursion

Write a program to solve the **0-1 Knapsack problem** using the recursion. In this program, you will learn how to solve the 0-1 Knapsack problem using the recursion.

## What is the 0-1 knapsack problem?

The knapsack problem may be a problem in combinatorial optimization:

- Given a group of things, each with a weight and a worth, determine the amount of every item included during a collection in order that the entire weight is a smaller amount than or adequate to a given limit and therefore the total value is as large as possible.
- It must fill it with the foremost valuable items and It derives its name from the matter faced by someone who is constrained by a fixed-size knapsack.
- The matter often arises in resource allocation where the decision-makers need to choose between a group of non-divisible projects or tasks under a hard and fast budget or time constraint, respectively.

## 0-1 knapsack problem definition:

The most common problem being solved is that the **0-1 knapsack problem**, which restricts the amount ** x_{i}** of copies of every quiet item to zero or one. Given a group of

**items numbered from 1 up to**

*n***, each with a weight**

*n***and a worth**

*w*_{i}**, alongside a maximum weight capacity**

*v*_{i}**.**

*W*

Implementation in the __c language__:

```
// Write a program to solve the 0-1 Knapsack problem using the recursion in c language
#include <stdio.h>
int maxSize(int a, int b);
int solveKnapSack(int W, int wt[], int val[], int n);
int main()
{
int val[] = { 60,
100,
120
}, wt[] = { 10,
20,
30
}, W = 50;
int n = sizeof(val) / sizeof(val[0]);
// This will print the solution of 0-1 Knapsack problem
printf("The solution of 0-1 Knapsack problem is: %d\n", solveKnapSack(W, wt, val, n));
return 0;
}
int maxSize(int a, int b)
{
return (a > b) ? a : b;
}
int solveKnapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return solveKnapSack(W, wt, val, n - 1);
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else
return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1));
}
```

**Output:**

`The solution of 0-1 Knapsack problem is: 220`

Implementation in the __c++ language__:

```
// Write a program to solve the 0-1 Knapsack problem using the recursion in c++ language
#include <iostream>
using namespace std;
int maxSize(int a, int b);
int solveKnapSack(int W, int wt[], int val[], int n);
int main()
{
int val[] = { 60,
100,
120
}, wt[] = { 10,
20,
30
}, W = 50;
int n = sizeof(val) / sizeof(val[0]);
// This will print the solution of 0-1 Knapsack problem
cout << "The solution of 0-1 Knapsack problem is: " << solveKnapSack(W, wt, val, n) << "\n";
return 0;
}
int maxSize(int a, int b)
{
return (a > b) ? a : b;
}
int solveKnapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return solveKnapSack(W, wt, val, n - 1);
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else
return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1));
}
```

**Output:**

`The solution of 0-1 Knapsack problem is: 220`

Implementation in the __java language__:

```
// Write a program to solve the 0-1 Knapsack problem
// using the recursion in java language
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Main main = new Main();
int[] val = {
60,
100,
120
};
int[] wt = {
10,
20,
30
};
int W = 50;
int n = val.length;
// This will print the solution of 0-1 Knapsack problem
System.out.println("The solution of 0-1 Knapsack problem is: " + main.solveKnapSack(W, wt, val, n));
}
int solveKnapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return this.solveKnapSack(W, wt, val, n - 1);
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else
return this.maxSize(val[n - 1] + this.solveKnapSack(W - wt[n - 1], wt, val, n - 1), this.solveKnapSack(W, wt, val, n - 1));
}
int maxSize(int a, int b) {
return (a > b) ? a : b;
}
}
```

**Output:**

`The solution of 0-1 Knapsack problem is: 220`

Implementation in the __python language__:

```
# Write a program to solve the 0-1 Knapsack problem using the recursion in python language
import sys
def maxSize(a, b):
pass
return a if a > b else b
def solveKnapSack(W, wt, val, n):
pass
if n == 0 or W == 0:
return 0
# 1. If the weight of the nth item is more than
# 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if wt[n - 1] > W:
return solveKnapSack(W, wt, val, n - 1)
# It returns the maximum of two cases:
# 1. nth item included
# 2. not included
else:
return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1))
val, wt, W = [60, 100, 120], [10, 20, 30], 50
n = int (sys.getsizeof(val) / sys.getsizeof(val[0]))
# This will print the solution of 0-1 Knapsack problem
print ("The solution of 0-1 Knapsack problem is: ", solveKnapSack(W, wt, val, n))
```

**Output:**

`The solution of 0-1 Knapsack problem is: 220`

Implementation in __PHP language__:

```
<?php
// Write a program to solve the 0-1 Knapsack problem using the recursion in PHP language
function maxSize($a, $b) {
return $a > $b ? $a : $b;
}
function solveKnapSack($W, $wt = [], $val = [], $n) {
if ($n == 0 || $W == 0) {
return 0;
}
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if ($wt[$n - 1] > $W) {
return solveKnapSack($W, $wt, $val, $n - 1);
}
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else {
return maxSize($val[$n - 1] + solveKnapSack($W - $wt[$n - 1], $wt, $val, $n - 1), solveKnapSack($W, $wt, $val, $n - 1));
}
}
$val = [60, 100, 120];
$wt = [10, 20, 30];
$W = 50;
$n = intval (sizeof($val) / sizeof($val[0]));
// This will print the solution of 0-1 Knapsack problem
echo "The solution of 0-1 Knapsack problem is: " . solveKnapSack($W, $wt, $val, $n);
?>
```

**Output:**

`The solution of 0-1 Knapsack problem is: 220`

## Tags:

# 0/1 knapsack problem using the greedy method

# 0/1 knapsack problem using dynamic programming example

# 0/1 knapsack problem using backtracking