Skip to main content

0-1 knapsack problem using dynamic programming

Here given code implementation process.

/*
    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
Last updated on by Kalkicode




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