/* A Naive recursive implementation of  0-1 Knapsack problem */ #include  using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // kan worden geplaatst in een knapzak met capaciteit W int knapSack(int W, int wt[], int val[], int n) // Basisscenario if (n == 0 // Stuurprogrammacode int main() { int winst[] = { 60, 100, 120 }; int gewicht[] = { 10, 20, 30 }; 0]);<< knapSack(W, weight, profit, n);  return 0; } // This code is contributed by rathbhupendra>

/* A Naive recursive implementation of 0-1 Knapsack problem */ #include  // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die kan worden // in een knapzak met capaciteit W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Als het gewicht van het n-de item groter is dan // Knapzakcapaciteit W, dan kan dit item niet // worden opgenomen in de optimale oplossing als (wt[n - 1]> W) knapSack(W, wt, val, n) retourneert - 1);  // Retourneer het maximum van twee gevallen: // (1) n-de item inbegrepen // (2) niet inbegrepen else return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapzak(W, wt, val, n - 1));  // Stuurprogrammacode int main() { int winst[] = { 60, 100, 120 };  int gewicht[] = { 10, 20, 30 };  int W = 50;  int n = groottevan(winst) / groottevan(winst[0]);  printf('%d', knapSack(W, gewicht, winst, n));  retour 0; }>

/* A Naive recursive implementation of 0-1 Knapsack problem */ class Knapsack {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // in een knapzak kan worden gestopt met // capaciteit W static int knapSack(int W, int wt[], int val[], int n) // Stuurprogrammacode public static void main( String args[]) { int winst[] = nieuwe int[] { 60, 100, 120 };  int gewicht[] = nieuwe int[] { 10, 20, 30 };  int W = 50;  int n = winst.lengte;  System.out.println(knapSack(W, gewicht, winst, n));  } } /*Deze code is bijgedragen door Rajat Mishra */>

# A naive recursive implementation # of 0-1 Knapsack Problem # Returns the maximum value that # can be put in a knapsack of # capacity W def knapSack(W, wt, val, n): # Base Case if n == 0 or W == 0: return 0 # If weight of the nth item is # more than Knapsack of capacity W, # then this item cannot be included # in the optimal solution if (wt[n-1]>W): retour knapSack(W, wt, val, n-1) # retourneer het maximum van twee gevallen: # (1) nde item inbegrepen # (2) niet inbegrepen anders: return max( val[n-1] + knapSack ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # einde van functie knapSack # Stuurprogrammacode if __name__ == '__main__': winst = [60, 100, 120] gewicht = [10, 20, 30] W = 50 n = len(winst) print knapSack(W, gewicht, winst, n) # Deze code is bijgedragen door Nikhil Kumar Singh>

/* A Naive recursive implementation of 0-1 Knapsack problem */ using System; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // in een knapzak met capaciteit W kan worden gestopt static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Als het gewicht van het n-de item // meer is dan Knapzakcapaciteit W, // dan kan dit item niet // opgenomen worden in de optimale oplossing als (wt[n - 1]> W) knapSack(W, wt, val) retourneert , n-1);  // Retourneer het maximum van twee gevallen: // (1) n-de item inbegrepen // (2) niet inbegrepen else return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapzak(W, wt, val, n - 1));    // Stuurprogrammacode public static void Main() { int[] winst = new int[] { 60, 100, 120 };  int[] gewicht = nieuw int[] { 10, 20, 30 };  int W = 50;  int n = winst.Lengte;  Console.WriteLine(knapSack(W, gewicht, winst, n));  } } // Deze code is bijgedragen door Sam007>

 /* A Naive recursive implementation of  0-1 Knapsack problem */    // A utility function that returns  // maximum of two integers  function max(a, b)  {  return (a>B) ? a: b;  } // Geeft de maximale waarde terug die // kan worden geplaatst in een knapzak met capaciteit W-functie knapSack(W, wt, val, n) // Basisscenario if (n == 0 laat winst = [ 60, 100, 120 ] ; laat gewicht = [ 10, 20, 30 ]; laat n = winst.lengte;PHP220>

Tijdcomplexiteit: O(2^N)
Hulpruimte: O(N), stapelruimte vereist voor recursie

Dynamische programmeerbenadering voor 0/1 knapzakprobleem

Memoisatiebenadering voor 0/1 knapzakprobleem:

Opmerking: Opgemerkt moet worden dat de bovenstaande functie met behulp van recursie dezelfde subproblemen keer op keer berekent. Zie de volgende recursieboom: K(1, 1) wordt twee keer geëvalueerd.

In de volgende recursieboom, K() verwijst naar knapSack(). De twee parameters die in de volgende recursieboom worden aangegeven, zijn n en W.
De recursieboom is bedoeld voor het volgen van voorbeeldinvoer.
gewicht[] = {1, 1, 1}, W = 2, winst[] = {10, 20, 30}

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)

Recursieboom voor Knapzakcapaciteit 2 eenheden en 3 items van 1 eenheidsgewicht.

Omdat hetzelfde deelprobleem keer op keer wordt herhaald, kunnen we het volgende idee implementeren om het probleem op te lossen.

Als we de eerste keer een subprobleem tegenkomen, kunnen we dit probleem oplossen door een 2D-array te maken die een bepaalde toestand (n, w) kan opslaan. Als we nu dezelfde toestand (n, w) opnieuw tegenkomen in plaats van deze in exponentiële complexiteit te berekenen, kunnen we direct het resultaat ervan retourneren dat in constante tijd in de tabel is opgeslagen.

hoekig materiaal

Hieronder vindt u de implementatie van de bovenstaande aanpak:

// Here is the top-down approach of // dynamic programming #include  using namespace std; // Returns the value of maximum profit int knapSackRec(int W, int wt[], int val[], int index, int** dp) {  // base condition  if (index < 0)  return 0;  if (dp[index][W] != -1)  return dp[index][W];  if (wt[index]>W) {/ // Bewaar de waarde van de functieaanroep // stapel in tabel vóór terugkeer dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  retourneer dp[index][W];  } else { // Bewaar waarde in een tabel vóór retournering dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , gew, val, index - 1, dp));  // Retourwaarde van tabel na opslaan return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // dubbele pointer om de // tabel dynamisch te declareren int** dp;  dp = nieuwe int*[n];  // lus om de tabel dynamisch te maken voor (int i = 0; i< n; i++)  dp[i] = new int[W + 1];  // loop to initially filled the  // table with -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); } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; }>

// Here is the top-down approach of // dynamic programming import java.io.*; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a: b; } // Retourneert de waarde van de maximale winst static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  als (dp[n][W] != -1) retourneert dp[n][W];  if (wt[n - 1]> W) // Bewaar de waarde van de functieaanroep // stapel in tabel vóór return return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Retourwaarde van tabel na opslaan 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) {// De tabel dynamisch declareren int dp[][] = new int[N + 1][W + 1];  // Loop om de // tabel aanvankelijk te vullen met -1 voor (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);  }  // Driver Code  public static void main(String[] args)  {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int N = profit.length;  System.out.println(knapSack(W, weight, profit, N));  } } // This Code is contributed By FARAZ AHMAD>

# This is the memoization approach of # 0 / 1 Knapsack in Python in simple # we can say recursion + memoization = DP def knapsack(wt, val, W, n): # base conditions if n == 0 or W == 0: return 0 if t[n][W] != -1: return t[n][W] # choice diagram code 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] = knapzak(wt, val, W, n-1) return t[n][W] # Chauffeurscode if __name__ == '__main__': winst = [60, 100, 120] gewicht = [10, 20, 30] W = 50 n = len(winst) # We initialiseren de matrix eerst met -1. t = [[-1 voor i binnen bereik(W + 1)] voor j binnen bereik(n + 1)] print(knapzak(gewicht, winst, W, n)) # Deze code is bijgedragen door Prosun Kumar Sarkar>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>B) ? a: b;  } // Retourneert de waarde van de maximale winstfunctie knapSackRec(W, wt, val, n,dp) // Basisvoorwaarde if (n == 0 functie knapSack( W, wt,val,N) {// Declareer de dp-tabel dynamisch // dp-tabellen (rij en kolommen) initialiseren met -1 onder var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); return knapSackRec(W, wt, var, N, dp); } var winst= [ 60, 100, 120 ]; ; console.log(knapSack(W, gewicht, winst, N)); // Deze code is bijgedragen door akshitsaxenaa09>
   
  Uitvoer  
220>
 
    Tijdcomplexiteit:    O(N * W). Omdat redundante berekeningen van toestanden worden vermeden.  
    Hulpruimte:    O(N * W) + O(N). Het gebruik van een 2D-array-datastructuur voor het opslaan van tussentoestanden en O(N) hulpstapelruimte (ASS) is gebruikt voor recursiestapel
 
    Bottom-up benadering voor het 0/1 knapzakprobleem:    
Om het probleem op te lossen, volgt u het onderstaande idee:
  
Omdat subproblemen opnieuw worden geëvalueerd, heeft dit probleem de eigenschap Overlappende subproblemen. Het 0/1 Knapzakprobleem heeft dus beide eigenschappen (zie dit En dit ) van een dynamisch programmeerprobleem. Net als andere typische Dynamische programmeerproblemen (DP). , kan herberekening van dezelfde subproblemen worden vermeden door een tijdelijke array K[][] op een bottom-up manier te construeren.
 
    Illustratie:    
 
Hieronder ziet u de illustratie van de bovenstaande aanpak:
  
Laten,    gewicht[] = {1, 2, 3}, winst[] = {10, 15, 40}, capaciteit = 6    
 
Als er geen element is gevuld, is de mogelijke winst 0.
gewicht⇢  
artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Voor het vullen van het eerste item in de tas:    Als we de bovengenoemde procedure volgen, ziet de tabel er als volgt uit.
gewicht⇢  
artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Voor het vullen van het tweede item:       
Wanneer jthWeight = 2, dan is de maximaal mogelijke winst max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Wanneer jthWeight = 3, dan is de maximaal mogelijke winst max(2 niet gedaan, 2 wordt in de zak gestopt) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
gewicht⇢  
artikel⇣/
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
vijftien
25
25
25
25
3
 
 
 
 
 
 
 
    Voor het vullen van het derde item:     
Wanneer jthWeight = 3, is de maximaal mogelijke winst max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Wanneer jthWeight = 4, is de maximaal mogelijke winst max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Wanneer jthWeight = 5, is de maximaal mogelijke winst max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Wanneer jthWeight = 6, is de maximaal mogelijke winst max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
gewicht⇢  
artikel⇣/
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
vijftien
25
25
25
25
3
0
10
vijftien
40
vijftig
55
65
Hieronder vindt u de implementatie van de bovenstaande aanpak:
C++ 
// A dynamic programming based // solution for 0-1 Knapsack problem #include  using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // in een knapzak met capaciteit W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vector> K(n + 1, vector (W+1));  // Bouw tabel K[][] bottom-up voor (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W]; } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; } // This code is contributed by Debojyoti Mandal>
 C 
// A Dynamic Programming based // solution for 0-1 Knapsack problem #include  // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // in een knapzak met capaciteit W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n+1][W+1];  // Bouw tabel K[][] bottom-up voor (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W]; } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', knapSack(W, weight, profit, n));  return 0; }>
 Java 
// A Dynamic Programming based solution // for 0-1 Knapsack problem import java.io.*; class Knapsack {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // in een knapzak met capaciteit W kan worden gestopt static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = nieuwe int[n + 1][W + 1];  // Bouw tabel K[][] bottom-up voor (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W];  }  // Driver code  public static void main(String args[])  {  int profit[] = new int[] { 60, 100, 120 };  int weight[] = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.println(knapSack(W, weight, profit, n));  } } /*This code is contributed by Rajat Mishra */>
 Python 
# A Dynamic Programming based Python # Program for 0-1 Knapsack problem # Returns the maximum value that can # be put in a knapsack of capacity W def knapSack(W, wt, val, n): K = [[0 for x in range(W + 1)] for x in range(n + 1)] # Build table K[][] in bottom up manner 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] # Driver code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print(knapSack(W, weight, profit, n)) # This code is contributed by Bhavya Jain>
 C# 
// A Dynamic Programming based solution for // 0-1 Knapsack problem using System; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a: b; } // Geeft de maximale waarde terug die // in een knapzak met // capaciteit W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = nieuwe int[n + 1, W + 1];  // Bouw tabel K[][] onderaan // omhoog voor (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   }  return K[n, W];  }  // Driver code  static void Main()  {  int[] profit = new int[] { 60, 100, 120 };  int[] weight = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.WriteLine(knapSack(W, weight, profit, n));  } } // This code is contributed by Sam007>
 Javascript 
 // A Dynamic Programming based solution  // for 0-1 Knapsack problem    // A utility function that returns  // maximum of two integers  function max(a, b)  {  return (a>B) ? a: b;  } // Geeft de maximale waarde terug die // in een knapzak met capaciteit kan worden gestopt W function knapSack(W, wt, val, n) { let i, w;  laat K = nieuwe array(n + 1);    // Bouw tabel K[][] bottom-up voor (i = 0; i<= n; i++)  {  K[i] = new Array(W + 1);  for (w = 0; w <= W; w++)   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 profit = [ 60, 100, 120 ];  let weight = [ 10, 20, 30 ];  let W = 50;  let n = profit.length;  console.log(knapSack(W, weight, profit, n));>
 PHP 
 // A Dynamic Programming based solution // for 0-1 Knapsack problem // Returns the maximum value that // can be put in a knapsack of  // capacity W function knapSack($W, $wt, $val, $n) { $K = array(array()); // Build table K[][] in // bottom up manner for ($i = 0; $i <= $n; $i++) { for ($w = 0; $w <= $W; $w++)  } return $K[$n][$W]; } // Driver Code $profit = array(60, 100, 120); $weight = array(10, 20, 30); $W = 50; $n = count($profit); echo knapSack($W, $weight, $profit, $n); // This code is contributed by Sam007. ?>>
   
  Uitvoer  
220>
 
    Tijdcomplexiteit:    O(N * W). waarbij ‘N’ het aantal elementen is en ‘W’ de capaciteit is.  
    Hulpruimte:    O(N * W). Het gebruik van een 2D-array met de grootte ‘N*W’.
fabrieksontwerppatroon
 
    Ruimte-geoptimaliseerde aanpak voor 0/1 knapzakprobleem met behulp van dynamisch programmeren:    
Om het probleem op te lossen, volgt u het onderstaande idee:
  
Voor het berekenen van de huidige rij van de dp[]-array hebben we alleen de vorige rij nodig, maar als we de rijen van rechts naar links gaan doorlopen, kan dit met slechts één rij worden gedaan
 
Hieronder vindt u de implementatie van de bovenstaande aanpak:
C++ 
// C++ program for the above approach #include  using namespace std; // Function to find the maximum profit int knapSack(int W, int wt[], int val[], int n) {  // Making and initializing dp array  int dp[W + 1];  memset(dp, 0, sizeof(dp));  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { als (wt[i - 1]<= w)    // Finding the maximum value  dp[w] = max(dp[w],  dp[w - wt[i - 1]] + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W]; } // Driver code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; }>
 Java 
// Java program for the above approach import java.util.*; class GFG {  static int knapSack(int W, int wt[], int val[], int n)  {  // Making and initializing dp array  int[] dp = new int[W + 1];  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { als (wt[i - 1]<= w)  // Finding the maximum value  dp[w]  = Math.max(dp[w], dp[w - wt[i - 1]]  + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  public static void main(String[] args)  {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.print(knapSack(W, weight, profit, n));  } } // This code is contributed by gauravrajput1>
 Python 
# Python code to implement the above approach def knapSack(W, wt, val, n): # Making the dp array dp = [0 for i in range(W+1)] # Taking first i elements for i in range(1, n+1): # Starting from back, # so that we also have data of # previous computation when taking i-1 items for w in range(W, 0, -1): if wt[i-1] <= w: # Finding the maximum value dp[w] = max(dp[w], dp[w-wt[i-1]]+val[i-1]) # Returning the maximum value of knapsack return dp[W] # Driver code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print(knapSack(W, weight, profit, n)) # This code is contributed by Suyash Saxena>
 C# 
// Java program for the above approach using System; public class GFG {  static int knapSack(int W, int[] wt, int[] val, int n)  {  // Making and initializing dp array  int[] dp = new int[W + 1];  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { als (wt[i - 1]<= w)  // Finding the maximum value  dp[w]  = Math.Max(dp[w], dp[w - wt[i - 1]]  + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  public static void Main(String[] args)  {  int[] profit = { 60, 100, 120 };  int[] weight = { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.Write(knapSack(W, weight, profit, n));  } } // This code is contributed by gauravrajput1>
 Javascript 
 function knapSack(W , wt , val , n)  {  // Making and initializing dp array  var dp = Array(W + 1).fill(0);  for (i = 1; i < n + 1; i++) {  for (w = W; w>= 0; w--) { als (wt[i - 1]<= w)  // Finding the maximum value  dp[w] = Math.max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);  }  }    // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  var profit = [ 60, 100, 120 ];  var weight = [ 10, 20, 30 ];  var W = 50;  var n = profit.length;  console.log(knapSack(W, weight, profit, n)); // This code is contributed by Rajput-Ji>
   
  Uitvoer  
220>
 
    Tijdcomplexiteit    : O(N * W). Omdat redundante toestandsberekeningen worden vermeden  
    Hulpruimte    : O(W) Omdat we een 1D-array gebruiken in plaats van een 2D-array