Solve 0/1 Knapsack Problem using Dynamic Programming
ADVERTISEMENTS
Solve 0/1 knapsack problem using dynamic programming. In this article, you will learn how to solve 0/1 knapsack problem using dynamic programming.
What is the 0-1 knapsack problem?
The knapsack problem may be a problem in combinatorial optimization:
- Given a group of things, each with a weight and a worth, determine the amount of every item included during a collection in order that the entire weight is a smaller amount than or adequate to a given limit and therefore the total value is as large as possible.
- It must fill it with the foremost valuable items and It derives its name from the matter faced by someone who is constrained by a fixed-size knapsack.
- The matter often arises in resource allocation where the decision-makers need to choose between a group of non-divisible projects or tasks under a hard and fast budget or time constraint, respectively.
0-1 knapsack problem definition:
The most common problem being solved is that the 0-1 knapsack problem, which restricts the amount xi of copies of every quiet item to zero or one.
Given a group of n items numbered from 1 up to n, each with a weight wi and a worth vi, alongside a maximum weight capacity W.
Source Code in C
// Solve 0/1 Knapsack Problem in C
#include <stdio.h>
int maxSize(int a, int b);
int solveKnapSack(int W, int wt[], int val[], int n);
// It's the driver function
int main() {
int val[] = { 60,
100,
120
}, wt[] = { 10,
20,
30
}, W = 50;
int n = sizeof(val) / sizeof(val[0]);
// This will print the solution of 0-1 Knapsack problem
printf("The solution of 0-1 Knapsack problem is: %d\n", solveKnapSack(W, wt, val, n));
return 0;
}
// This will return max size of the value
int maxSize(int a, int b) {
return (a > b) ? a : b;
}
// This function will solve the 0 1 knapsack problem
int solveKnapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return solveKnapSack(W, wt, val, n - 1);
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else
return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1));
}
Output
The solution of 0-1 Knapsack problem is: 220
Source Code in C++
// Solve 0/1 Knapsack Problem in C++
#include <iostream>
using namespace std;
int maxSize(int a, int b);
int solveKnapSack(int W, int wt[], int val[], int n);
// It's the driver function
int main() {
int val[] = { 60,
100,
120
}, wt[] = { 10,
20,
30
}, W = 50;
int n = sizeof(val) / sizeof(val[0]);
// This will print the solution of 0-1 Knapsack problem
cout << "The solution of 0-1 Knapsack problem is: " << solveKnapSack(W, wt, val, n) << "\n";
return 0;
}
// This will return max size of the value
int maxSize(int a, int b) {
return (a > b) ? a : b;
}
// This function will solve the 0 1 knapsack problem
int solveKnapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return solveKnapSack(W, wt, val, n - 1);
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else
return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1));
}
Output
The solution of 0-1 Knapsack problem is: 220
Source Code in Java
// Solve 0/1 Knapsack Problem in Java
import java.util.Scanner;
public class Main {
// It's the driver function
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Main main = new Main();
int[] val = {
60,
100,
120
};
int[] wt = {
10,
20,
30
};
int W = 50;
int n = val.length;
// This will print the solution of 0-1 Knapsack problem
System.out.println("The solution of 0-1 Knapsack problem is: " + main.solveKnapSack(W, wt, val, n));
}
// This function will solve the 0 1 knapsack problem
int solveKnapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return this.solveKnapSack(W, wt, val, n - 1);
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else
return this.maxSize(val[n - 1] + this.solveKnapSack(W - wt[n - 1], wt, val, n - 1), this.solveKnapSack(W, wt, val, n - 1));
}
// This will return max size of the value
int maxSize(int a, int b) {
return (a > b) ? a : b;
}
}
Output
The solution of 0-1 Knapsack problem is: 220
Source Code in Python
# Solve 0/1 Knapsack Problem in Python
import sys
# This will return max size of the value
def maxSize(a, b):
pass
return a if a > b else b
# This function will solve the 0 1 knapsack problem
def solveKnapSack(W, wt, val, n):
pass
if n == 0 or W == 0:
return 0
# 1. If the weight of the nth item is more than
# 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if wt[n - 1] > W:
return solveKnapSack(W, wt, val, n - 1)
# It returns the maximum of two cases:
# 1. nth item included
# 2. not included
else:
return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1))
# It's the driver code
val, wt, W = [60, 100, 120], [10, 20, 30], 50
n = int (sys.getsizeof(val) / sys.getsizeof(val[0]))
# This will print the solution of 0-1 Knapsack problem
print ("The solution of 0-1 Knapsack problem is: ", solveKnapSack(W, wt, val, n))
Output
The solution of 0-1 Knapsack problem is: 220
Source Code in PHP
<?php
// Solve 0/1 Knapsack Problem in PHP
// This will return max size of the value
function maxSize($a, $b) {
return $a > $b ? $a : $b;
}
// This function will solve the 0 1 knapsack problem
function solveKnapSack($W, $wt = [], $val = [], $n) {
if ($n == 0 || $W == 0) {
return 0;
}
// 1. If the weight of the nth item is more than
// 2. Knapsack capacity W, then this item cannot be included in the optimal solution
if ($wt[$n - 1] > $W) {
return solveKnapSack($W, $wt, $val, $n - 1);
}
// It returns the maximum of two cases:
// 1. nth item included
// 2. not included
else {
return maxSize($val[$n - 1] + solveKnapSack($W - $wt[$n - 1], $wt, $val, $n - 1), solveKnapSack($W, $wt, $val, $n - 1));
}
}
// It's the driver code
$val = [60, 100, 120];
$wt = [10, 20, 30];
$W = 50;
$n = intval (sizeof($val) / sizeof($val[0]));
// This will print the solution of 0-1 Knapsack problem
echo "The solution of 0-1 Knapsack problem is: " . solveKnapSack($W, $wt, $val, $n);
?>
Output
The solution of 0-1 Knapsack problem is: 220