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[0]);
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[0]);
// 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)
{
KnapSack task = new KnapSack();
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
task.knapSackSolution(capacity, weights, values, n);
}
}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()
{
KnapSack *task = new KnapSack();
int values[] = {
10 , 40 , 30 , 50
};
int weights[] = {
5 , 4 , 6 , 3
};
// Get the number of elements
int n = sizeof(values) / sizeof(values[0]);
// Capacity
int capacity = 10;
// Test
task->knapSackSolution(capacity, weights, values, n);
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)
{
KnapSack task = new KnapSack();
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
task.knapSackSolution(capacity, weights, values, n);
}
}Output
90package 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()
{
$task = new KnapSack();
$values = array(10, 40, 30, 50);
$weights = array(5, 4, 6, 3);
// Get the number of elements
$n = count($values);
// Capacity
$capacity = 10;
// Test
$task->knapSackSolution($capacity, $weights, $values, $n);
}
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 task = new KnapSack();
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
task.knapSackSolution(capacity, weights, values, n);
}
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 = [[0] * (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() :
task = KnapSack()
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
# Get the number of elements
n = len(values)
# Capacity
capacity = 10
# Test
task.knapSackSolution(capacity, weights, values, n)
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()
task = KnapSack.new()
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
# Get the number of elements
n = values.length
# Capacity
capacity = 10
# Test
task.knapSackSolution(capacity, weights, values, n)
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
task.knapSackSolution(capacity, weights, values, n);
}
}Output
90import 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 task: KnapSack = KnapSack();
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
task.knapSackSolution(capacity, weights, values, n);
}
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 task: KnapSack = KnapSack();
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
task.knapSackSolution(capacity, weights, values, n);
}Output
90Time 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.
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.
New Comment