0/1 PROBLEMĂ LA RUCSAC

Cerințe preliminare: Introducere în problema rucsacului, tipurile acesteia și cum să le rezolvi

Dat N articole în care fiecare articol are o greutate și un profit asociat și, de asemenea, li se oferă o pungă cu capacitate ÎN , [adică, geanta poate ține cel mult ÎN greutate în ea]. Sarcina este de a pune articolele în pungă astfel încât suma profiturilor asociate acestora să fie maximă posibilă.

Notă: Constrângerea aici este că putem fie să punem un articol complet în pungă, fie că nu îl putem pune deloc [Nu este posibil să punem o parte a unui articol în geantă].

Exemple:

Intrare: N = 3, W = 4, profit[] = {1, 2, 3}, greutate[] = {4, 5, 1}
Ieșire: 3
Explicaţie: Există două articole care au pondere mai mică sau egală cu 4. Dacă selectăm articolul cu ponderea 4, profitul posibil este 1. Și dacă selectăm articolul cu pondere 1, profitul posibil este 3. Deci, profitul maxim posibil este 3. Rețineți că nu putem pune împreună ambele articole cu greutatea 4 și 1, deoarece capacitatea genții este de 4.

Intrare: N = 3, W = 3, profit[] = {1, 2, 3}, greutate[] = {4, 5, 6}
Ieșire: 0

Practică recomandată 0 – 1 Problemă la rucsac Încercați!

Abordarea recursiunii pentru problema rucsacului 0/1:

Pentru a rezolva problema urmați ideea de mai jos:

O soluție simplă este să luați în considerare toate subseturile de articole și să calculați ponderea totală și profitul tuturor subsețiilor. Luați în considerare singurele subseturi a căror greutate totală este mai mică decât W. Din toate astfel de subseturi, alegeți submulțimea cu profit maxim.
tipuri de arbore binar

Substructură optimă : Pentru a lua în considerare toate subseturile de articole, pot exista două cazuri pentru fiecare articol.

Cazul 1: Articolul este inclus în subsetul optim.
Cazul 2: Articolul nu este inclus în setul optim.

Urmați pașii de mai jos pentru a rezolva problema:

Valoarea maximă obținută din „N” articole este valoarea maximă a următoarelor două valori.

Cazul 1 (includeți N^thelement): valoarea N^tharticol plus valoarea maximă obținută prin N-1 articole rămase și greutatea rămasă, adică (greutatea W a N^tharticol).
Cazul 2 (excluderea N^thitem): Valoarea maximă obținută de N-1 articole și greutate W.
Dacă greutatea lui ‘N^th„elementul este mai mare decât „W”, atunci al N-lea element nu poate fi inclus și Cazul 2 este singura posibilitate.

Mai jos este implementarea abordării de mai sus:

C++

 /* 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; } // Returnează valoarea maximă pe care // poate fi pusă într-un rucsac de capacitate W int knapSack(int W, int wt[], int val[], int n) // Caz de bază dacă (n == 0 // Cod driver int main() { int profit[] = { 60, 100, 120 } int weight[] = { 10, 20, 30 } int n = sizeof(profit) / sizeof(profit; 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; } // Returnează valoarea maximă care poate fi // pusă într-un rucsac de capacitate W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Dacă greutatea celui de-al n-lea articol este mai mare decât // Capacitatea rucsacului W, atunci acest articol nu poate // fi inclus în soluția optimă dacă (wt[n - 1]> W) returnează rucsac(W, wt, val, n - 1);  // Returnează maximum două cazuri: // (1) al-lea articol inclus // (2) neinclus altfel return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), rucsac (W, wt, val, n - 1));  // Cod driver int main() { int profit[] = { 60, 100, 120 };  int greutate[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', knapSack(W, greutate, profit, n));  întoarce 0; }>>>Java # 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): returnează sac (W, wt, val, n-1) # returnează maximum două cazuri: # (1) al-lea articol inclus # (2) nu este inclus altfel: return max( val[n-1] + sac ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # sfârşitul funcţiei KnapSack # Cod driver dacă __name__ == '__main__': profit = [60, 100, 120] greutate = [10, 20, 30] W = 50 n = len(profit) print knapSack(W, weight, profit, n) # Acest cod este contribuit de Nikhil Kumar Singh>
 C# /* 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; } // Returnează valoarea maximă care poate // fi pusă într-un rucsac de capacitate W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Dacă greutatea celui de-al n-lea articol este // mai mare decât capacitatea rucsacului W, // atunci acest articol nu poate fi // inclus în soluția optimă dacă (wt[n - 1]> W) returnează rucsac(W, wt, val , n - 1);  // Returnează maximum două cazuri: // (1) al-lea articol inclus // (2) neinclus altfel return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), rucsac (W, wt, val, n - 1));    // Cod driver public static void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] greutate = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.Lungime;  Console.WriteLine(knapSack(W, greutate, profit, n));  } } // Acest cod este contribuit de Sam007>>>Javascript$W) returnează sac($W, $wt, $val, $n - 1); // Returnează maximum două cazuri: // (1) al-lea articol inclus // (2) neinclus altfel returnează max($val[$n - 1] + knapSack($W - $wt[$n - 1] , $wt, $val, $n - 1), KnapSack($W, $wt, $val, $n-1));  // Cod driver $profit = array(60, 100, 120); $greutate = matrice(10, 20, 30); $W = 50; $n = count($profit); echo knapSack($W, $greutate, $profit, $n); // Acest cod este contribuit de Sam007 ?>>
   
  Ieșire  220>
     Complexitatea timpului:    O(2^N)  
    Spațiu auxiliar:    O(N), spațiu de stivă necesar pentru recursivitate
 Abordare de programare dinamică pentru problema rucsacului 0/1
Abordarea memorării pentru problema rucsacului 0/1:
    Notă:    Trebuie remarcat faptul că funcția de mai sus folosind recursiunea calculează aceleași subprobleme din nou și din nou. Vedeți următorul arbore recursiv, K(1, 1) este evaluat de două ori.
  În următorul arbore recursiv,    K()    se referă la knapSack(). Cei doi parametri indicați în următorul arbore recursiv sunt n și W.  
Arborele recursiv este pentru următoarele eșantion de intrare.  
greutate[] = {1, 1, 1}, W = 2, profit[] = {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)
 Arborele recursiv pentru Rucsac de capacitate 2 unități și 3 articole de 1 unitate de greutate.
 
Deoarece există repetări ale aceleiași subprobleme din nou și din nou, putem implementa următoarea idee pentru a rezolva problema.
  Dacă primim o subproblemă prima dată, putem rezolva această problemă prin crearea unui tablou 2-D care poate stoca o anumită stare (n, w). Acum, dacă întâlnim din nou aceeași stare (n, w) în loc să o calculăm în complexitate exponențială, putem returna direct rezultatul stocat în tabel în timp constant.
java main
 
Mai jos este implementarea abordării de mai sus:
C++ // 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) { // Stocați valoarea apelului de funcție // stivuiți în tabel înainte de returnarea dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  returnează dp[index][W];  } else { // Stocați valoarea într-un tabel înainte de returnarea dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , wt, val, index - 1, dp));  // Returnează valoarea tabelului după stocarea return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // indicator dublu pentru a declara // tabelul dinamic int** dp;  dp = new int*[n];  // buclă pentru a crea tabelul dinamic pentru (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; }>
 Java // 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; } // Returnează valoarea profitului maxim static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  dacă (dp[n][W] != -1) returnează dp[n][W];  if (wt[n - 1]> W) // Stochează valoarea apelului funcției // stivuiește în tabel înainte de return return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Returnează valoarea tabelului după stocarea 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) { // Declara tabelul dinamic int dp[][] = new int[N + 1][W + 1];  // Buclă pentru a completa inițial tabelul // cu -1 pentru (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>
 Piton # 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] = rucsac(wt, val, W, n-1) return t[n][W] # Cod șofer dacă __name__ == '__main__': profit = [60, 100, 120] greutate = [10, 20, 30] W = 50 n = len(profit) # Inițializam matricea cu -1 la început. t = [[-1 pentru i în interval (W + 1)] pentru j în interval (n + 1)] print(rucsac(greutate, profit, W, n)) # Acest cod este contribuit de Prosun Kumar Sarkar>'>C# // A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b) ? a:b;  } // Returnează valoarea funcției de profit maxim knapSackRec(W, wt, val, n,dp) // Condiția de bază dacă (n == 0 funcția knapSack( W, wt,val,N) { // Declarați tabelul dp dinamic // Inițializarea tabelelor dp (rând și coloane) cu -1 sub var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); return knapSackRec(W, wt, val, N, dp } var profit= [ 60, 100, 120 ] var W = 50; ; console.log(knapSack(W, weight, profit, N) // Acest cod este contribuit de akshitsaxenaa09  
  Ieșire  220>
      Complexitatea timpului:    O(N * W). Deoarece calculele redundante ale stărilor sunt evitate.  
    Spațiu auxiliar:    O(N * W) + O(N). Utilizarea unei structuri de date matrice 2D pentru stocarea stărilor intermediare și a spațiului de stivă auxiliar O(N) (ASS) a fost utilizată pentru stiva de recursivitate
alternative watchcartoononline.io
     Abordare de jos în sus pentru problema rucsacului 0/1:    
Pentru a rezolva problema urmați ideea de mai jos:
  Deoarece subproblemele sunt evaluate din nou, această problemă are proprietatea Subprobleme suprapuse. Deci problema rucsacului 0/1 are ambele proprietăți (vezi acest și acest ) unei probleme de programare dinamică. Ca și alte tipice Probleme de programare dinamică (DP). , recalcularea acelorași subprobleme poate fi evitată prin construirea unui tablou temporar K[][] într-o manieră de jos în sus.
 
    Ilustrare:    
 Mai jos este ilustrarea abordării de mai sus:
  Lăsa,    greutate[] = {1, 2, 3}, profit[] = {10, 15, 40}, Capacitate = 6    
 Dacă nu este completat niciun element, atunci profitul posibil este 0.
greutate⇢  
articol⇣/ 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1        
2        
3        
    Pentru umplerea primului articol din pungă:    Dacă urmam procedura menționată mai sus, tabelul va arăta ca următorul.
greutate⇢  
articol⇣/ 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        
    Pentru completarea celui de-al doilea articol:       
Când jthWeight = 2, atunci profitul maxim posibil este max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Când jthWeight = 3, atunci profitul maxim posibil este max(2 nu sunt puse, 2 sunt puse în pungă) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
greutate⇢  
articol⇣/ 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 cincisprezece 25 25 25 25
3        
    Pentru completarea celui de-al treilea articol:     
Când jthWeight = 3, profitul maxim posibil este max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Când jthWeight = 4, profitul maxim posibil este max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Când jthWeight = 5, profitul maxim posibil este max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Când jthWeight = 6, profitul maxim posibil este max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
greutate⇢  
articol⇣/ 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 cincisprezece 25 25 25 25
3 0 10 cincisprezece 40 cincizeci 55 65
Mai jos este implementarea abordării de mai sus:
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; } // Returnează valoarea maximă pe care // o poate pune într-un rucsac de capacitate W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vector> K(n + 1, vector (W + 1));  // Construiește tabelul K[][] de jos în sus pentru (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; } // Returnează valoarea maximă pe care // o poate pune într-un rucsac de capacitate W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Construiește tabelul K[][] de jos în sus pentru (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; } // Returnează valoarea maximă care poate // fi pusă într-un rucsac de capacitate W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = new int[n + 1][W + 1];  // Construiește tabelul K[][] de jos în sus pentru (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 */>
 Piton # 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; } // Returnează valoarea maximă pe care // o poate pune într-un rucsac de // capacitate W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = nou int[n + 1, W + 1];  // Construiți tabelul K[][] în jos // în sus pentru (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;  } // Returnează valoarea maximă care poate // fi pusă într-un rucsac de capacitate W function knapSack(W, wt, val, n) { let i, w;  fie K = new Array(n + 1);    // Construiește tabelul K[][] de jos în sus pentru (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. ?>>>>  
  Ieșire      Complexitatea timpului:    O(N * W). unde „N” este numărul de elemente și „W” este capacitatea.  
    Spațiu auxiliar:    O(N * W). Utilizarea unei matrice 2-D de dimensiunea „N*W”.
     Abordare optimizată pentru spațiu pentru problema de rucsac 0/1 folosind programarea dinamică:    
Pentru a rezolva problema urmați ideea de mai jos:
  Pentru a calcula rândul curent al matricei dp[] avem nevoie doar de rândul anterior, dar dacă începem să parcurgem rândurile de la dreapta la stânga atunci se poate face doar cu un singur rând.
 
Mai jos este implementarea abordării de mai sus:
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--) { dacă (greutate [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--) { dacă (greutate [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>
 Piton # 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--) { dacă (greutate [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--) { dacă (greutate [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>
   
  Ieșire      Complexitatea timpului    : O(N * W). Deoarece calculele redundante ale stărilor sunt evitate  
    Spațiu auxiliar    : O(W) Deoarece folosim o matrice 1-D în loc de o matrice 2-D

TechCodeview

Abordarea recursiunii pentru problema rucsacului 0/1:

Abordare de programare dinamică pentru problema rucsacului 0/1

Abordarea memorării pentru problema rucsacului 0/1:

Abordare de jos în sus pentru problema rucsacului 0/1:

Abordare optimizată pentru spațiu pentru problema de rucsac 0/1 folosind programarea dinamică:

greutate⇢ articol⇣/	1	2	3	4	5	6
0	0	0	0	0	0	0
1	10	10	10	10	10	10
2	10	cincisprezece	25	25	25	25
3	10	cincisprezece	40	cincizeci	55	65