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