Posted on by Kalkicode
Code Dynamic Programming

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

 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()
{
	$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

 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 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

 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.

New Comment