# 0-1 knapsack problem using dynamic programming

The 0-1 Knapsack problem is a classic optimization problem in computer science and mathematics. It involves selecting items with certain weights and values to maximize the total value while ensuring that the total weight does not exceed a given capacity. This problem has various applications, such as resource allocation, financial investments, and project scheduling.

## Problem Statement

Given a set of items, each with a weight and a value, and a knapsack with a limited weight capacity, the task is to determine the maximum total value that can be obtained by selecting a subset of the items to include in the knapsack.

## Pseudocode Algorithm

The 0-1 Knapsack problem can be efficiently solved using dynamic programming. The following pseudocode explains the algorithm step by step:

``````
function knapSackSolution(capacity, weights[], values[], n):
record[n+1][capacity+1]

for i = 0 to n:
for w = 0 to capacity:
if i = 0 or w = 0:
record[i][w] = 0
else if weights[i-1] <= w:
record[i][w] = max(values[i-1] + record[i-1][w - weights[i-1]], record[i-1][w])
else:
record[i][w] = record[i-1][w]

return record[n][capacity]
``````

The algorithm uses a 2D array, `record`, to store the maximum value achieved at each combination of items and knapsack capacities. It iterates through all possible item and capacity combinations, considering two cases: including the current item or excluding it. The maximum value is stored in the `record` array, which is then returned as the result.

## Explanation with Example

Let's illustrate the algorithm with an example:

``````
int values[] = {10, 40, 30, 50};
int weights[] = {5, 4, 6, 3};
int n = sizeof(values) / sizeof(values);
int capacity = 10;

knapSackSolution(capacity, weights, values, n);
``````

In this example, we have four items with their respective weights and values. The capacity of the knapsack is 10. After executing the `knapSackSolution` function, the output will be `90`.

The algorithm calculates the maximum value that can be achieved by considering all possible combinations of items and capacities. In the end, it returns the maximum value obtained.

## Code Solution

``````/*
C program for
0-1 knapsack problem using dynamic programming
*/
#include <stdio.h>

int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void knapSackSolution(int capacity, int weights[], int values[], int n)
{
int record[n + 1][capacity + 1];
for (int i = 0; i <= n; i++)
{
for (int w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i][w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i][w] = maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w]);
}
else
{
record[i][w] = record[i - 1][w];
}
}
}
printf(" %d \n", record[n][capacity]);
}
int main(int argc, char
const *argv[])
{
int values[] = {
10 , 40 , 30 , 50
};
int weights[] = {
5 , 4 , 6 , 3
};
// Get the number of elements
int n = sizeof(values) / sizeof(values);
// Capacity
int capacity = 10;
// Test
knapSackSolution(capacity, weights, values, n);
return 0;
}``````

#### Output

`` 90``
``````/*
Java Program for
0-1 knapsack problem using dynamic programming
*/
public class KnapSack
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void knapSackSolution(int capacity, int[] weights,
int[] values, int n)
{
// Auxiliary space
int[][] record = new int[n + 1][capacity + 1];
for (int i = 0; i <= n; i++)
{
for (int w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i][w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i][w] = maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w]);
}
else
{
record[i][w] = record[i - 1][w];
}
}
}
System.out.print(" " + record[n][capacity] + " \n");
}
public static void main(String[] args)
{
int[] values = {
10 , 40 , 30 , 50
};
int[] weights = {
5 , 4 , 6 , 3
};
// Get the number of elements
int n = values.length;
// Capacity
int capacity = 10;
// Test
}
}``````

#### Output

`` 90``
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
0-1 knapsack problem using dynamic programming
*/
class KnapSack
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void knapSackSolution(int capacity, int weights[], int values[], int n)
{
// Auxiliary space
int record[n + 1][capacity + 1];
for (int i = 0; i <= n; i++)
{
for (int w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i][w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i][w] = this->maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w]);
}
else
{
record[i][w] = record[i - 1][w];
}
}
}
cout << " " << record[n][capacity] << " \n";
}
};
int main()
{
int values[] = {
10 , 40 , 30 , 50
};
int weights[] = {
5 , 4 , 6 , 3
};
// Get the number of elements
int n = sizeof(values) / sizeof(values);
// Capacity
int capacity = 10;
// Test
return 0;
}``````

#### Output

`` 90``
``````// Include namespace system
using System;
/*
Csharp Program for
0-1 knapsack problem using dynamic programming
*/
public class KnapSack
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void knapSackSolution(int capacity,
int[] weights, int[] values, int n)
{
// Auxiliary space
int[,] record = new int[n + 1,capacity + 1];
for (int i = 0; i <= n; i++)
{
for (int w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i,w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i,w] = this.maxValue(values[i - 1] +
record[i - 1,w - weights[i - 1]],
record[i - 1,w]);
}
else
{
record[i,w] = record[i - 1,w];
}
}
}
Console.Write(" " + record[n,capacity] + " \n");
}
public static void Main(String[] args)
{
int[] values = {
10 , 40 , 30 , 50
};
int[] weights = {
5 , 4 , 6 , 3
};
// Get the number of elements
int n = values.Length;
// Capacity
int capacity = 10;
// Test
}
}``````

#### Output

`` 90``
``````package main
import "fmt"
/*
Go Program for
0-1 knapsack problem using dynamic programming
*/

func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func knapSackSolution(capacity int, weights[] int, values[] int, n int) {
// Auxiliary space
var record = make([][]int, n + 1)
for i := range record {
record[i] = make([]int, capacity + 1)
}
for i := 0 ; i <= n ; i++ {
for w := 0 ; w <= capacity ; w++ {
if i == 0 || w == 0 {
// When of [i ]and [w] values are zero
record[i][w] = 0
} else if weights[i - 1] <= w {
record[i][w] = maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]], record[i - 1][w])
} else {
record[i][w] = record[i - 1][w]
}
}
}
fmt.Print(" ", record[n][capacity], " \n")
}
func main() {

var values = [] int { 10 , 40 , 30 , 50 }
var weights = [] int { 5 , 4 , 6 , 3 }
// Get the number of elements
var n int = len(values)
// Capacity
var capacity int = 10
// Test
knapSackSolution(capacity, weights, values, n)
}``````

#### Output

`` 90``
``````<?php
/*
Php Program for
0-1 knapsack problem using dynamic programming
*/
class KnapSack
{
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function knapSackSolution(\$capacity, \$weights, \$values, \$n)
{
// Auxiliary space
\$record = array_fill(0, \$n + 1, array_fill(0, \$capacity + 1, 0));
for (\$i = 0; \$i <= \$n; \$i++)
{
for (\$w = 0; \$w <= \$capacity; \$w++)
{
if (\$i == 0 || \$w == 0)
{
// When of [i ]and [w] values are zero
\$record[\$i][\$w] = 0;
}
else if (\$weights[\$i - 1] <= \$w)
{
\$record[\$i][\$w] = \$this->maxValue(
\$values[\$i - 1] +
\$record[\$i - 1][\$w - \$weights[\$i - 1]],
\$record[\$i - 1][\$w]);
}
else
{
\$record[\$i][\$w] = \$record[\$i - 1][\$w];
}
}
}
echo(" ".\$record[\$n][\$capacity].
" \n");
}
}

function main()
{
\$values = array(10, 40, 30, 50);
\$weights = array(5, 4, 6, 3);
// Get the number of elements
\$n = count(\$values);
// Capacity
\$capacity = 10;
// Test
}
main();``````

#### Output

`` 90``
``````/*
Node JS Program for
0-1 knapsack problem using dynamic programming
*/
class KnapSack
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
knapSackSolution(capacity, weights, values, n)
{
// Auxiliary space
var record = Array(n + 1).fill(0).map(
() => new Array(capacity + 1).fill(0));
for (var i = 0; i <= n; i++)
{
for (var w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i][w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i][w] = this.maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w]);
}
else
{
record[i][w] = record[i - 1][w];
}
}
}
process.stdout.write(" " + record[n][capacity] + " \n");
}
}

function main()
{
var values = [10, 40, 30, 50];
var weights = [5, 4, 6, 3];
// Get the number of elements
var n = values.length;
// Capacity
var capacity = 10;
// Test
}
main();``````

#### Output

`` 90``
``````#    Python 3 Program for
#    0-1 knapsack problem using dynamic programming
class KnapSack :
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def knapSackSolution(self, capacity, weights, values, n) :
#  Auxiliary space
record = [ * (capacity + 1) for _ in range(n + 1) ]
i = 0
while (i <= n) :
w = 0
while (w <= capacity) :
if (i == 0 or w == 0) :
#  When of [i ]and [w] values are zero
record[i][w] = 0
elif (weights[i - 1] <= w) :
record[i][w] = self.maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w])
else :
record[i][w] = record[i - 1][w]

w += 1

i += 1

print(" ", record[n][capacity] ," ")

def main() :
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
#  Get the number of elements
n = len(values)
#  Capacity
capacity = 10
#  Test

if __name__ == "__main__": main()``````

#### Output

``  90``
``````#    Ruby Program for
#    0-1 knapsack problem using dynamic programming
class KnapSack
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def knapSackSolution(capacity, weights, values, n)
#  Auxiliary space
record = Array.new(n + 1) {Array.new(capacity + 1) {0}}
i = 0
while (i <= n)
w = 0
while (w <= capacity)
if (i == 0 || w == 0)
#  When of [i ]and [w] values are zero
record[i][w] = 0
elsif (weights[i - 1] <= w)
record[i][w] = self.maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w])
else

record[i][w] = record[i - 1][w]
end

w += 1
end

i += 1
end

print(" ", record[n][capacity] ," \n")
end

end

def main()
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
#  Get the number of elements
n = values.length
#  Capacity
capacity = 10
#  Test
end

main()``````

#### Output

`````` 90
``````
``````/*
Scala Program for
0-1 knapsack problem using dynamic programming
*/
class KnapSack()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def knapSackSolution(capacity: Int, weights: Array[Int],
values: Array[Int], n: Int): Unit = {
// Auxiliary space
var record: Array[Array[Int]] = Array.fill[Int](n + 1, capacity + 1)(0);
var i: Int = 0;
while (i <= n)
{
var w: Int = 0;
while (w <= capacity)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record(i)(w) = 0;
}
else if (weights(i - 1) <= w)
{
record(i)(w) = maxValue(values(i - 1) +
record(i - 1)(w - weights(i - 1)),
record(i - 1)(w));
}
else
{
record(i)(w) = record(i - 1)(w);
}
w += 1;
}
i += 1;
}
print(" " + record(n)(capacity) + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: KnapSack = new KnapSack();
var values: Array[Int] = Array(10, 40, 30, 50);
var weights: Array[Int] = Array(5, 4, 6, 3);
// Get the number of elements
var n: Int = values.length;
// Capacity
var capacity: Int = 10;
// Test
}
}``````

#### Output

`` 90``
``````import Foundation;
/*
Swift 4 Program for
0-1 knapsack problem using dynamic programming
*/
class KnapSack
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func knapSackSolution(_ capacity: Int,
_ weights: [Int], _ values: [Int], _ n: Int)
{
// Auxiliary space
var record: [
[Int]
] = Array(repeating: Array(repeating: 0,
count: capacity + 1), count: n + 1);
var i: Int = 0;
while (i <= n)
{
var w: Int = 0;
while (w <= capacity)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i][w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i][w] = self.maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w]);
}
else
{
record[i][w] = record[i - 1][w];
}
w += 1;
}
i += 1;
}
print(" ", record[n][capacity] ," ");
}
}
func main()
{
let values: [Int] = [10, 40, 30, 50];
let weights: [Int] = [5, 4, 6, 3];
// Get the number of elements
let n: Int = values.count;
// Capacity
let capacity: Int = 10;
// Test
}
main();``````

#### Output

``  90``
``````/*
Kotlin Program for
0-1 knapsack problem using dynamic programming
*/
class KnapSack
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun knapSackSolution(capacity: Int, weights: Array < Int > ,
values: Array < Int > , n: Int): Unit
{
// Auxiliary space
val record: Array < Array < Int >> = Array(n + 1)
{
Array(capacity + 1)
{
0
}
};
var i: Int = 0;
while (i <= n)
{
var w: Int = 0;
while (w <= capacity)
{
if (i == 0 || w == 0)
{
// When of [i ]and [w] values are zero
record[i][w] = 0;
}
else if (weights[i - 1] <= w)
{
record[i][w] = this.maxValue(values[i - 1] +
record[i - 1][w - weights[i - 1]],
record[i - 1][w]);
}
else
{
record[i][w] = record[i - 1][w];
}
w += 1;
}
i += 1;
}
print(" " + record[n][capacity] + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val values: Array < Int > = arrayOf(10, 40, 30, 50);
val weights: Array < Int > = arrayOf(5, 4, 6, 3);
// Get the number of elements
val n: Int = values.count();
// Capacity
val capacity: Int = 10;
// Test
}``````

#### Output

`` 90``

## Time Complexity

The time complexity of the dynamic programming solution for the 0-1 Knapsack problem is `O(n * capacity)`, where `n` is the number of items and `capacity` is the capacity of the knapsack. The algorithm iterates through all possible combinations once, resulting in a polynomial time complexity.

## Finally

The 0-1 Knapsack problem is efficiently solved using dynamic programming. By considering all possible combinations of items and capacities, the algorithm determines the maximum total value that can be achieved without exceeding the knapsack's capacity. The provided example demonstrates the application of this algorithm, and the time complexity analysis assures its efficiency.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.