Consider the Following Continuous Knapsack Problem
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don't pick it (0-1 property).
Method 1: Recursion by Brute-Force algorithm OR Exhaustive Search.
Approach: A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.
Optimal Sub-structure : To consider all subsets of items, there can be two cases for every item.
- Case 1: The item is included in the optimal subset.
- Case 2: The item is not included in the optimal set.
Therefore, the maximum value that can be obtained from 'n' items is the max of the following two values.
- Maximum value obtained by n-1 items and W weight (excluding nth item).
- Value of nth item plus maximum value obtained by n-1 items and W minus the weight of the nth item (including nth item).
If the weight of 'nth' item is greater than 'W', then the nth item cannot be included and Case 1 is the only possibility.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int max( int a, int b) { return (a > b) ? a : b; }
int knapSack( int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1],
wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
C
#include <stdio.h>
int max( int a, int b) { return (a > b) ? a : b; }
int knapSack( int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1],
wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
printf ( "%d" , knapSack(W, wt, val, n));
return 0;
}
Java
class Knapsack {
static int max( int a, int b)
{
return (a > b) ? a : b;
}
static int knapSack( int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0 )
return 0 ;
if (wt[n - 1 ] > W)
return knapSack(W, wt, val, n - 1 );
else
return max(val[n - 1 ]
+ knapSack(W - wt[n - 1 ], wt,
val, n - 1 ),
knapSack(W, wt, val, n - 1 ));
}
public static void main(String args[])
{
int val[] = new int [] { 60 , 100 , 120 };
int wt[] = new int [] { 10 , 20 , 30 };
int W = 50 ;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Python
def knapSack(W, wt, val, n):
if n = = 0 or W = = 0 :
return 0
if (wt[n - 1 ] > W):
return knapSack(W, wt, val, n - 1 )
else :
return max (
val[n - 1 ] + knapSack(
W - wt[n - 1 ], wt, val, n - 1 ),
knapSack(W, wt, val, n - 1 ))
val = [ 60 , 100 , 120 ]
wt = [ 10 , 20 , 30 ]
W = 50
n = len (val)
print knapSack(W, wt, val, n)
C#
using System;
class GFG {
static int max( int a, int b)
{
return (a > b) ? a : b;
}
static int knapSack( int W, int [] wt,
int [] val, int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt,
val, n - 1);
else
return max(val[n - 1]
+ knapSack(W - wt[n - 1], wt,
val, n - 1),
knapSack(W, wt, val, n - 1));
}
public static void Main()
{
int [] val = new int [] { 60, 100, 120 };
int [] wt = new int [] { 10, 20, 30 };
int W = 50;
int n = val.Length;
Console.WriteLine(knapSack(W, wt, val, n));
}
}
PHP
<?php
function knapSack( $W , $wt , $val , $n )
{
if ( $n == 0 || $W == 0)
return 0;
if ( $wt [ $n - 1] > $W )
return knapSack( $W , $wt , $val , $n - 1);
else
return max( $val [ $n - 1] +
knapSack( $W - $wt [ $n - 1],
$wt , $val , $n - 1),
knapSack( $W , $wt , $val , $n -1));
}
$val = array (60, 100, 120);
$wt = array (10, 20, 30);
$W = 50;
$n = count ( $val );
echo knapSack( $W , $wt , $val , $n );
?>
Javascript
<script>
function max(a, b)
{
return (a > b) ? a : b;
}
function knapSack(W, wt, val, n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n - 1] +
knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
let val = [ 60, 100, 120 ];
let wt = [ 10, 20, 30 ];
let W = 50;
let n = val.length;
document.write(knapSack(W, wt, val, n));
</script>
It should be noted that the above function computes the same sub-problems again and again. See the following recursion tree, K(1, 1) is being evaluated twice. The time complexity of this naive recursive solution is exponential (2^n).
In the following recursion tree, K() refers to knapSack(). The two parameters indicated in the following recursion tree are n and W. The recursion tree is for following sample inputs. wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30} K(n, W) K(3, 2) / \ / \ K(2, 2) K(2, 1) / \ / \ / \ / \ K(1, 2) K(1, 1) K(1, 1) K(1, 0) / \ / \ / \ / \ / \ / \ K(0, 2) K(0, 1) K(0, 1) K(0, 0) K(0, 1) K(0, 0) Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight. Complexity Analysis:
- Time Complexity: O(2n).
As there are redundant subproblems. - Auxiliary Space :O(1) + O(N).
As no extra data structure has been used for storing values but O(N) auxiliary stack space(ASS) has been used for recursion stack.
Since subproblems are evaluated again, this problem has Overlapping Sub-problems property. So the 0-1 Knapsack problem has both properties (see this and this) of a dynamic programming problem.
Method 2: Like other typical Dynamic Programming(DP) problems, re-computation of same subproblems can be avoided by constructing a temporary array K[][] in bottom-up manner. Following is Dynamic Programming based implementation.
Approach: In the Dynamic programming we will work considering the same cases as mentioned in the recursive approach. In a DP[][] table let's consider all the possible weights from '1' to 'W' as the columns and weights that can be kept as the rows.
The state DP[i][j] will denote maximum value of 'j-weight' considering all values from '1 to ith'. So if we consider 'wi' (weight in 'ith' row) we can fill it in all columns which have 'weight values > wi'. Now two possibilities can take place:
- Fill 'wi' in the given column.
- Do not fill 'wi' in the given column.
Now we have to take a maximum of these two possibilities, formally if we do not fill 'ith' weight in 'jth' column then DP[i][j] state will be same as DP[i-1][j] but if we fill the weight, DP[i][j] will be equal to the value of 'wi'+ value of the column weighing 'j-wi' in the previous row. So we take the maximum of these two possibilities to fill the current state. This visualisation will make the concept clear:
Let weight elements = {1, 2, 3} Let weight values = {10, 15, 40} Capacity=6 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 10 10 10 10 10 10 2 0 10 15 25 25 25 25 3 0 Explanation: For filling 'weight = 2' we come across 'j = 3' in which we take maximum of (10, 15 + DP[1][3-2]) = 25 | | '2' '2 filled' not filled 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 10 10 10 10 10 10 2 0 10 15 25 25 25 25 3 0 10 15 40 50 55 65 Explanation: For filling 'weight=3', we come across 'j=4' in which we take maximum of (25, 40 + DP[2][4-3]) = 50 For filling 'weight=3' we come across 'j=5' in which we take maximum of (25, 40 + DP[2][5-3]) = 55 For filling 'weight=3' we come across 'j=6' in which we take maximum of (25, 40 + DP[2][6-3]) = 65 C++
#include <bits/stdc++.h>
using namespace std;
int max( int a, int b)
{
return (a > b) ? a : b;
}
int knapSack( int W, int wt[], int val[], int n)
{
int i, w;
vector<vector< int >> K(n + 1, vector< int >(W + 1));
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]],
K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
C
#include <stdio.h>
int max( int a, int b)
{
return (a > b) ? a : b;
}
int knapSack( int W, int wt[], int val[], int n)
{
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1]
+ K[i - 1][w - wt[i - 1]],
K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
printf ( "%d" , knapSack(W, wt, val, n));
return 0;
}
Java
class Knapsack {
static int max( int a, int b)
{
return (a > b) ? a : b;
}
static int knapSack( int W, int wt[],
int val[], int n)
{
int i, w;
int K[][] = new int [n + 1 ][W + 1 ];
for (i = 0 ; i <= n; i++)
{
for (w = 0 ; w <= W; w++)
{
if (i == 0 || w == 0 )
K[i][w] = 0 ;
else if (wt[i - 1 ] <= w)
K[i][w]
= max(val[i - 1 ]
+ K[i - 1 ][w - wt[i - 1 ]],
K[i - 1 ][w]);
else
K[i][w] = K[i - 1 ][w];
}
}
return K[n][W];
}
public static void main(String args[])
{
int val[] = new int [] { 60 , 100 , 120 };
int wt[] = new int [] { 10 , 20 , 30 };
int W = 50 ;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Python
def knapSack(W, wt, val, n):
K = [[ 0 for x in range (W + 1 )] for x in range (n + 1 )]
for i in range (n + 1 ):
for w in range (W + 1 ):
if i = = 0 or w = = 0 :
K[i][w] = 0
elif wt[i - 1 ] < = w:
K[i][w] = max (val[i - 1 ]
+ K[i - 1 ][w - wt[i - 1 ]],
K[i - 1 ][w])
else :
K[i][w] = K[i - 1 ][w]
return K[n][W]
val = [ 60 , 100 , 120 ]
wt = [ 10 , 20 , 30 ]
W = 50
n = len (val)
print (knapSack(W, wt, val, n))
C#
using System;
class GFG {
static int max( int a, int b)
{
return (a > b) ? a : b;
}
static int knapSack( int W, int [] wt,
int [] val, int n)
{
int i, w;
int [, ] K = new int [n + 1, W + 1];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i, w] = 0;
else if (wt[i - 1] <= w)
K[i, w] = Math.Max(
val[i - 1]
+ K[i - 1, w - wt[i - 1]],
K[i - 1, w]);
else
K[i, w] = K[i - 1, w];
}
}
return K[n, W];
}
static void Main()
{
int [] val = new int [] { 60, 100, 120 };
int [] wt = new int [] { 10, 20, 30 };
int W = 50;
int n = val.Length;
Console.WriteLine(knapSack(W, wt, val, n));
}
}
PHP
<?php
function knapSack( $W , $wt , $val , $n )
{
$K = array ( array ());
for ( $i = 0; $i <= $n ; $i ++)
{
for ( $w = 0; $w <= $W ; $w ++)
{
if ( $i == 0 || $w == 0)
$K [ $i ][ $w ] = 0;
else if ( $wt [ $i - 1] <= $w )
$K [ $i ][ $w ] = max( $val [ $i - 1] +
$K [ $i - 1][ $w -
$wt [ $i - 1]],
$K [ $i - 1][ $w ]);
else
$K [ $i ][ $w ] = $K [ $i - 1][ $w ];
}
}
return $K [ $n ][ $W ];
}
$val = array (60, 100, 120);
$wt = array (10, 20, 30);
$W = 50;
$n = count ( $val );
echo knapSack( $W , $wt , $val , $n );
?>
Javascript
<script>
function max(a, b)
{
return (a > b) ? a : b;
}
function knapSack(W, wt, val, n)
{
let i, w;
let K = new Array(n + 1);
for (i = 0; i <= n; i++)
{
K[i] = new Array(W + 1);
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w]
= max(val[i - 1]
+ K[i - 1][w - wt[i - 1]],
K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
let val = [ 60, 100, 120 ];
let wt = [ 10, 20, 30 ];
let W = 50;
let n = val.length;
document.write(knapSack(W, wt, val, n));
</script>
Complexity Analysis:
- Time Complexity: O(N*W).
where 'N' is the number of weight element and 'W' is capacity. As for every weight element we traverse through all weight capacities 1<=w<=W. - Auxiliary Space: O(N*W).
The use of 2-D array of size 'N*W'.
Scope for Improvement :-We used the same approach but with optimized space complexity
C++
#include <bits/stdc++.h>
using namespace std;
int knapSack( int W, int wt[], int val[], int n)
{
int i, w;
int K[2][W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i % 2][w] = 0;
else if (wt[i - 1] <= w)
K[i % 2][w] = max(
val[i - 1]
+ K[(i - 1) % 2][w - wt[i - 1]],
K[(i - 1) % 2][w]);
else
K[i % 2][w] = K[(i - 1) % 2][w];
}
}
return K[n % 2][W];
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
Java
import java.util.*;
class GFG {
static int knapSack( int W, int wt[], int val[], int n)
{
int i, w;
int [][]K = new int [ 2 ][W + 1 ];
for (i = 0 ; i <= n; i++) {
for (w = 0 ; w <= W; w++) {
if (i == 0 || w == 0 )
K[i % 2 ][w] = 0 ;
else if (wt[i - 1 ] <= w)
K[i % 2 ][w] = Math.max(
val[i - 1 ]
+ K[(i - 1 ) % 2 ][w - wt[i - 1 ]],
K[(i - 1 ) % 2 ][w]);
else
K[i % 2 ][w] = K[(i - 1 ) % 2 ][w];
}
}
return K[n % 2 ][W];
}
public static void main(String[] args)
{
int val[] = { 60 , 100 , 120 };
int wt[] = { 10 , 20 , 30 };
int W = 50 ;
int n = val.length;
System.out.print(knapSack(W, wt, val, n));
}
}
Python3
def knapSack(W, wt, val, n):
K = [[ 0 for x in range (W + 1 )] for y in range ( 2 )]
for i in range (n + 1 ):
for w in range (W + 1 ):
if (i = = 0 or w = = 0 ):
K[i % 2 ][w] = 0
elif (wt[i - 1 ] < = w):
K[i % 2 ][w] = max (
val[i - 1 ]
+ K[(i - 1 ) % 2 ][w - wt[i - 1 ]],
K[(i - 1 ) % 2 ][w])
else :
K[i % 2 ][w] = K[(i - 1 ) % 2 ][w]
return K[n % 2 ][W]
if __name__ = = "__main__" :
val = [ 60 , 100 , 120 ]
wt = [ 10 , 20 , 30 ]
W = 50
n = len (val)
print (knapSack(W, wt, val, n))
C#
using System;
public class GFG {
static int knapSack( int W, int []wt, int []val, int n) {
int i, w;
int [,] K = new int [2,W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i % 2, w] = 0;
else if (wt[i - 1] <= w)
K[i % 2,w] = Math.Max(val[i - 1] + K[(i - 1) % 2,w - wt[i - 1]], K[(i - 1) % 2,w]);
else
K[i % 2,w] = K[(i - 1) % 2,w];
}
}
return K[n % 2,W];
}
public static void Main(String[] args) {
int []val = { 60, 100, 120 };
int []wt = { 10, 20, 30 };
int W = 50;
int n = val.Length;
Console.Write(knapSack(W, wt, val, n));
}
}
Javascript
<script>
function knapSack(W , wt , val , n) {
var i, w;
var K = Array(2).fill().map(()=>Array(W + 1).fill(0));
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i % 2][w] = 0;
else if (wt[i - 1] <= w)
K[i % 2][w] = Math.max(val[i - 1] +
K[(i - 1) % 2][w - wt[i - 1]],
K[(i - 1) % 2][w]);
else
K[i % 2][w] = K[(i - 1) % 2][w];
}
}
return K[n % 2][W];
}
var val = [ 60, 100, 120 ];
var wt = [ 10, 20, 30 ];
var W = 50;
var n = val.length;
document.write(knapSack(W, wt, val, n));
</script>
Complexity Analysis:
- Time Complexity: O(N*W).
- Auxiliary Space: O(2*W)
As we are using a 2-D array but with only 2 rows.
Method 3: This method uses Memoization Technique (an extension of recursive approach).
This method is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus increased complexity. We can solve this problem by simply creating a 2-D array that can store a particular state (n, w) if we get it the first time. Now if we come across the same state (n, w) again instead of calculating it in exponential complexity we can directly return its result stored in the table in constant time. This method gives an edge over the recursive approach in this aspect.
C++
#include <bits/stdc++.h>
using namespace std;
int knapSackRec( int W, int wt[],
int val[], int i,
int ** dp)
{
if (i < 0)
return 0;
if (dp[i][W] != -1)
return dp[i][W];
if (wt[i] > W) {
dp[i][W] = knapSackRec(W, wt,
val, i - 1,
dp);
return dp[i][W];
}
else {
dp[i][W] = max(val[i]
+ knapSackRec(W - wt[i],
wt, val,
i - 1, dp),
knapSackRec(W, wt, val,
i - 1, dp));
return dp[i][W];
}
}
int knapSack( int W, int wt[], int val[], int n)
{
int ** dp;
dp = new int *[n];
for ( int i = 0; i < n; i++)
dp[i] = new int [W + 1];
for ( int i = 0; i < n; i++)
for ( int j = 0; j < W + 1; j++)
dp[i][j] = -1;
return knapSackRec(W, wt, val, n - 1, dp);
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
Java
class GFG{
static int max( int a, int b)
{
return (a > b) ? a : b;
}
static int knapSackRec( int W, int wt[],
int val[], int n,
int [][]dp)
{
if (n == 0 || W == 0 )
return 0 ;
if (dp[n][W] != - 1 )
return dp[n][W];
if (wt[n - 1 ] > W)
return dp[n][W] = knapSackRec(W, wt, val,
n - 1 , dp);
else
return dp[n][W] = max((val[n - 1 ] +
knapSackRec(W - wt[n - 1 ], wt,
val, n - 1 , dp)),
knapSackRec(W, wt, val,
n - 1 , dp));
}
static int knapSack( int W, int wt[], int val[], int N)
{
int dp[][] = new int [N + 1 ][W + 1 ];
for ( int i = 0 ; i < N + 1 ; i++)
for ( int j = 0 ; j < W + 1 ; j++)
dp[i][j] = - 1 ;
return knapSackRec(W, wt, val, N, dp);
}
public static void main(String [] args)
{
int val[] = { 60 , 100 , 120 };
int wt[] = { 10 , 20 , 30 };
int W = 50 ;
int N = val.length;
System.out.println(knapSack(W, wt, val, N));
}
}
Python3
val = [ 60 , 100 , 120 ]
wt = [ 10 , 20 , 30 ]
W = 50
n = len (val)
t = [[ - 1 for i in range (W + 1 )] for j in range (n + 1 )]
def knapsack(wt, val, W, n):
if n = = 0 or W = = 0 :
return 0
if t[n][W] ! = - 1 :
return t[n][W]
if wt[n - 1 ] < = W:
t[n][W] = max (
val[n - 1 ] + knapsack(
wt, val, W - wt[n - 1 ], n - 1 ),
knapsack(wt, val, W, n - 1 ))
return t[n][W]
elif wt[n - 1 ] > W:
t[n][W] = knapsack(wt, val, W, n - 1 )
return t[n][W]
print (knapsack(wt, val, W, n))
C#
using System;
public class GFG
{
static int max( int a, int b) { return (a > b) ? a : b; }
static int knapSackRec( int W, int [] wt, int [] val,
int n, int [, ] dp)
{
if (n == 0 || W == 0)
return 0;
if (dp[n, W] != -1)
return dp[n, W];
if (wt[n - 1] > W)
return dp[n, W]
= knapSackRec(W, wt, val, n - 1, dp);
else
return dp[n, W]
= max((val[n - 1]
+ knapSackRec(W - wt[n - 1], wt, val,
n - 1, dp)),
knapSackRec(W, wt, val, n - 1, dp));
}
static int knapSack( int W, int [] wt, int [] val, int N)
{
int [, ] dp = new int [N + 1, W + 1];
for ( int i = 0; i < N + 1; i++)
for ( int j = 0; j < W + 1; j++)
dp[i, j] = -1;
return knapSackRec(W, wt, val, N, dp);
}
static public void Main()
{
int [] val = new int []{ 60, 100, 120 };
int [] wt = new int []{ 10, 20, 30 };
int W = 50;
int N = val.Length;
Console.WriteLine(knapSack(W, wt, val, N));
}
}
Javascript
<script>
function max(a, b)
{
return (a > b) ? a : b;
}
function knapSackRec(W, wt, val, n,dp)
{
if (n == 0 || W == 0)
return 0;
if (dp[n][W] != -1)
return dp[n][W];
if (wt[n - 1] > W)
return dp[n][W] = knapSackRec(W, wt, val,
n - 1, dp);
else
return dp[n][W] = max((val[n - 1] +
knapSackRec(W - wt[n - 1], wt,
val, n - 1, dp)),
knapSackRec(W, wt, val,
n - 1, dp));
}
function knapSack( W, wt,val,N)
{
var dp = new Array(N + 1);
for ( var i = 0; i < dp.length; i++)
{
dp[i]= new Array(W + 1);
}
for ( var i = 0; i < N + 1; i++)
for ( var j = 0; j < W + 1; j++)
dp[i][j] = -1;
return knapSackRec(W, wt, val, N, dp);
}
var val= [ 60, 100, 120 ];
var wt = [ 10, 20, 30 ];
var W = 50;
var N = val.length;
document.write(knapSack(W, wt, val, N));
</script>
Complexity Analysis:
- Time Complexity: O(N*W).
As redundant calculations of states are avoided. - Auxiliary Space: O(N*W) + O(N).
The use of 2D array data structure for storing intermediate states and O(N) auxiliary stack space(ASS) has been used for recursion stack:
[Note: For 32bit integer use long instead of int.]
References:
- http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
- http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf
- https://youtu.be/T4bY72lCQac?list=PLqM7alHXFySGMu2CSdW_6d2u1o6WFTIO-
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Method 4 :- Again we use the dynamic programming approach with even more optimized space complexity .
C++
#include <bits/stdc++.h>
using namespace std;
int knapSack( int W, int wt[], int val[], int n)
{
int dp[W + 1];
memset (dp, 0, sizeof (dp));
for ( int i = 1; i < n + 1; i++) {
for ( int w = W; w >= 0; w--) {
if (wt[i - 1] <= w)
dp[w] = max(dp[w],
dp[w - wt[i - 1]] + val[i - 1]);
}
}
return dp[W];
}
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof (val) / sizeof (val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
Java
import java.util.*;
class GFG{
static int knapSack( int W, int wt[], int val[], int n)
{
int []dp = new int [W + 1 ];
for ( int i = 1 ; i < n + 1 ; i++) {
for ( int w = W; w >= 0 ; w--) {
if (wt[i - 1 ] <= w)
dp[w] = Math.max(dp[w],
dp[w - wt[i - 1 ]] + val[i - 1 ]);
}
}
return dp[W];
}
public static void main(String[] args)
{
int val[] = { 60 , 100 , 120 };
int wt[] = { 10 , 20 , 30 };
int W = 50 ;
int n = val.length;
System.out.print(knapSack(W, wt, val, n));
}
}
Python3
def knapSack(W, wt, val, n):
dp = [ 0 for i in range (W + 1 )]
for i in range ( 1 , n + 1 ):
for w in range (W, 0 , - 1 ):
if wt[i - 1 ] < = w:
dp[w] = max (dp[w], dp[w - wt[i - 1 ]] + val[i - 1 ])
return dp[W]
val = [ 60 , 100 , 120 ]
wt = [ 10 , 20 , 30 ]
W = 50
n = len (val)
print (knapSack(W, wt, val, n))
C#
using System;
public class GFG {
static int knapSack( int W, int []wt, int []val, int n)
{
int [] dp = new int [W + 1];
for ( int i = 1; i < n + 1; i++)
{
for ( int w = W; w >= 0; w--)
{
if (wt[i - 1] <= w)
dp[w] = Math.Max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
}
}
return dp[W];
}
public static void Main(String[] args) {
int []val = { 60, 100, 120 };
int []wt = { 10, 20, 30 };
int W = 50;
int n = val.Length;
Console.Write(knapSack(W, wt, val, n));
}
}
Javascript
<script>
function knapSack(W , wt , val , n)
{
var dp = Array(W + 1).fill(0);
for (i = 1; i < n + 1; i++) {
for (w = W; w >= 0; w--) {
if (wt[i - 1] <= w)
dp[w] = Math.max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
}
}
return dp[W];
}
var val = [ 60, 100, 120 ];
var wt = [ 10, 20, 30 ];
var W = 50;
var n = val.length;
document.write(knapSack(W, wt, val, n));
</script>
Complexity Analysis:
Time Complexity: O(N*W). As redundant calculations of states are avoided.
Auxiliary Space: O(W) As we are using 1-D array instead of 2-D array.
Source: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
0 Response to "Consider the Following Continuous Knapsack Problem"
Post a Comment