0/1 RULLESÆK PROBLEM

Forudsætninger: Introduktion til rygsækproblem, dets typer og hvordan man løser dem

Givet N varer, hvor hver vare har en vis vægt og overskud forbundet med sig og også givet en taske med kapacitet I , [dvs. posen kan højst rumme I vægt i det]. Opgaven er at lægge genstandene i posen, så summen af overskud forbundet med dem er størst muligt.

Bemærk: Begrænsningen her er, at vi enten kan putte en vare helt i posen eller slet ikke kan putte den [Det er ikke muligt at putte en del af en vare i posen].

Eksempler:

Input: N = 3, W = 4, overskud[] = {1, 2, 3}, vægt[] = {4, 5, 1}
Produktion: 3
Forklaring: Der er to varer, der har en vægt mindre end eller lig med 4. Hvis vi vælger varen med vægt 4, er den mulige fortjeneste 1. Og hvis vi vælger varen med vægt 1, er den mulige fortjeneste 3. Så den maksimalt mulige fortjeneste er 3. Bemærk at vi ikke kan lægge begge varer med vægt 4 og 1 sammen, da taskens kapacitet er 4.

Input: N = 3, W = 3, overskud[] = {1, 2, 3}, vægt[] = {4, 5, 6}
Produktion: 0

Anbefalet praksis 0 – 1 rygsækproblem Prøv det!

Rekursionstilgang til 0/1 rygsækproblem:

Følg nedenstående idé for at løse problemet:

En simpel løsning er at overveje alle delmængder af varer og beregne den samlede vægt og fortjeneste af alle delmængder. Overvej de eneste delmængder, hvis samlede vægt er mindre end W. Fra alle sådanne delmængder, vælg delmængden med maksimal fortjeneste.

læse fra csv-fil i java

Optimal underbygning : For at tage hensyn til alle undersæt af elementer, kan der være to tilfælde for hver vare.

Case 1: Varen indgår i den optimale delmængde.
Tilfælde 2: Varen er ikke inkluderet i det optimale sæt.

Følg nedenstående trin for at løse problemet:

Den maksimale værdi opnået fra 'N' elementer er maks. af de følgende to værdier.

Tilfælde 1 (inkluder N^thvare): Værdien af N^thvare plus maksimal værdi opnået ved resterende N-1 varer og resterende vægt, dvs. (W-vægt af N^thvare).
Tilfælde 2 (ekskluder N^thvare): Maksimal værdi opnået ved N-1 varer og W vægt.
Hvis vægten af 'N^th' vare er større end 'W', så kan den N. vare ikke inkluderes og Tilfælde 2 er den eneste mulighed.

Nedenfor er implementeringen af ovenstående tilgang:

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; } // Returnerer den maksimale værdi, som // kan lægges i en rygsæk med kapacitet W int knapSack(int W, int wt[], int val[], int n) // Base Case if (n == 0 // Driverkode int main() { int profit[] = { 60, 100, 120 } = { 10, 20, 30 }; int W = 50; 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; } // Returnerer den maksimale værdi, der kan // puttes i en rygsæk med kapacitet W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Hvis vægten af den n'te vare er mere end // Rygsækkapacitet W, så kan denne vare ikke // indgå i den optimale løsning, hvis (wt[n - 1]> W) return knapSack(W, wt, val, n - 1);  // Returner maksimalt to tilfælde: // (1) n'te vare inkluderet // (2) ikke inkluderet ellers return max( val[n - 1] + knapSæk(W - wt[n - 1], wt, val, n-1), knapSæk(W, wt, val, n-1));  // Driverkode int main() { int profit[] = { 60, 100, 120 };  int vægt[] = { 10, 20, 30 };  int W = 50;  int n = størrelse på(profit) / størrelse på(profit[0]);  printf('%d', knapSæk(W, vægt, profit, n));  retur 0; }>

Java

 /* 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; } // Returnerer den maksimale værdi, som // kan lægges i en rygsæk på // kapacitet W static int knapSack(int W, int wt[], int val[], int n) // Driver code public static void main( String args[]) { int profit[] = new int[] { 60, 100, 120 };  int vægt[] = ny int[] { 10, 20, 30 };  int W = 50;  int n = profit.længde;  System.out.println(knapSack(W, vægt, profit, n));  } } /*Denne kode er bidraget af Rajat Mishra */>

Python

 # 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): returner knapSæk(W, wt, val, n-1) # returner maksimalt to tilfælde: # (1) n. vare inkluderet # (2) ikke inkluderet andet: return max( val[n-1] + knapSæk ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # end of function knapSack # Driverkode hvis __navn__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print knapSack(W, weight, profit, n) # Denne kode er bidraget af 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; } // Returnerer den maksimale værdi, der kan // sættes i en rygsæk med kapacitet W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Hvis vægten af den n'te vare er // mere end Rygsækkens kapacitet W, // kan denne vare ikke // inkluderes i den optimale løsning hvis (wt[n - 1]> W) return knapSack(W, wt, val n-1);  // Returner maksimalt to tilfælde: // (1) n'te vare inkluderet // (2) ikke inkluderet ellers returner max(val[n - 1] + knapSæk(W - wt[n - 1], wt, val, n-1), knapSæk(W, wt, val, n-1));    // Driver code public static void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] vægt = ny int[] { 10, 20, 30 };  int W = 50;  int n = profit.Længde;  Console.WriteLine(knapSack(W, vægt, profit, n));  } } // Denne kode er bidraget af Sam007>

Javascript

  /* 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;  } // Returnerer den maksimale værdi, der kan // sættes i en rygsæk med kapacitet W-funktion knapSack(W, wt, val, n) // Base Case if (n == 0 lad profit = [ 60, 100, 120 ] ; lad vægt = [ 10, 20, 30 ]; lad n = fortjenestePHP>

Produktion

220>

Tidskompleksitet: O(2^N)
Hjælpeplads: O(N), Stakplads kræves til rekursion

Dynamisk programmeringstilgang til 0/1 knapsækproblem

Memoiseringsmetode for 0/1 knapsækproblem:

Bemærk: Det skal bemærkes, at ovenstående funktion ved hjælp af rekursion beregner de samme underproblemer igen og igen. Se følgende rekursionstræ, K(1, 1) evalueres to gange.

I det følgende rekursionstræ, K() henviser til knapSæk(). De to parametre, der er angivet i det følgende rekursionstræ, er n og W.
Rekursionstræet er til følgende eksempelinput.
vægt[] = {1, 1, 1}, W = 2, overskud[] = {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)

Rekursionstræ til Rullesæk kapacitet 2 enheder og 3 genstande af 1 vægtenhed.

Da der er gentagelser af det samme delproblem igen og igen, kan vi implementere følgende idé for at løse problemet.

Hvis vi får et underproblem første gang, kan vi løse dette problem ved at skabe et 2-D-array, der kan lagre en bestemt tilstand (n, w). Hvis vi nu støder på den samme tilstand (n, w) igen i stedet for at beregne den i eksponentiel kompleksitet, kan vi direkte returnere dets resultat gemt i tabellen i konstant tid.
10 af 60

Nedenfor er implementeringen af ovenstående tilgang:

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) { // Gem værdien af funktionskald // stak i tabel før returnering dp[indeks][W] = knapSackRec(W, wt, val, index - 1, dp);  returner dp[indeks][W];  } else { // Gem værdi i en tabel før returnering dp[indeks][W] = max(val[indeks] + knapSackRec(W - wt[indeks], wt, val, index - 1, dp), knapSackRec(W , vægt, val, indeks - 1, dp));  // Returner værdi af tabel efter lagring af return dp[indeks][W];  } } int knapSack(int W, int wt[], int val[], int n) { // dobbelt pointer til at erklære // tabellen dynamisk int** dp;  dp = ny int*[n];  // loop for at oprette tabellen dynamisk for (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; } // Returnerer værdien af maksimal profit statisk int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) returner dp[n][W];  if (wt[n - 1]> W) // Gem værdien af funktionskald // stack i tabel før returnering return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Returner værdi af tabellen efter lagring af 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) { // Erklære tabellen dynamisk int dp[][] = new int[N + 1][W + 1];  // Loop for at udfylde //-tabellen med -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);  }  // 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>

Python

# 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] = rygsæk(wt, val, W, n-1) returner t[n][W] # Førerkode hvis __navn__ == '__main__': profit = [60, 100, 120] vægt = [10, 20, 30] W = 50 n = len(profit) # Vi initialiserer matrixen med -1 først. t = [[-1 for i i område(W + 1)] for j i område(n + 1)] print(knapsack(vægt, overskud, W, n)) # Denne kode er bidraget af Prosun Kumar Sarkar>'>C# // A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b) ? a:b;  } // Returnerer værdien af funktionen maksimal profit knapSackRec(W, wt, val, n,dp) // Base condition if (n == 0 function knapSack( W, wt,val,N) { // Deklarer dp-tabellen dynamisk // Intialisering af dp-tabeller (række og kolonner) med -1 under 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 ]; ; console.log(knapSack(W, vægt, profit, N));  
  Produktion  220>
      Tidskompleksitet:    O(N * W). Da overflødige beregninger af tilstande undgås.  
    Hjælpeplads:    O(N * W) + O(N). Brugen af en 2D-array-datastruktur til lagring af mellemtilstande og O(N) auxiliary stack space(ASS) er blevet brugt til rekursionsstak
     Bottom-up tilgang til 0/1 Rullesæk-problem:    
Følg nedenstående idé for at løse problemet:
  Da underproblemer evalueres igen, har dette problem egenskaben Overlappende underproblemer. Så 0/1 Rullesæk-problemet har begge egenskaber (se det her og det her ) af et dynamisk programmeringsproblem. Som andre typiske Dynamisk programmering (DP) problemer , kan genberegning af de samme underproblemer undgås ved at konstruere et midlertidigt array K[][] på en bottom-up måde.
 
    Illustration:    
 Nedenfor er illustrationen af ovenstående fremgangsmåde:
  Lade,    vægt[] = {1, 2, 3}, overskud[] = {10, 15, 40}, Kapacitet = 6    
 Hvis intet element er udfyldt, er den mulige fortjeneste 0.
vægt⇢  
vare⇣/ 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1        
2        
3        
    For at fylde den første vare i posen:    Hvis vi følger ovennævnte procedure, vil tabellen se ud som følgende.
vægt⇢  
vare⇣/ 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        
    For at udfylde det andet punkt:       
Når jthWeight = 2, så er den maksimale mulige profit max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Når jthWeight = 3, så er den maksimale mulige fortjeneste max(2 ikke puttet, 2 puttes i posen) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
vægt⇢  
vare⇣/ 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 femten 25 25 25 25
3        
    For at udfylde det tredje punkt:     
Når jthWeight = 3, er den maksimalt mulige profit max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Når jthWeight = 4, er den maksimalt mulige profit max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Når jthWeight = 5, er den maksimalt mulige profit max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Når jthWeight = 6, er den maksimalt mulige profit max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
vægt⇢  
vare⇣/ 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 femten 25 25 25 25
3 0 10 femten 40 halvtreds 55 65
Nedenfor er implementeringen af ovenstående tilgang:
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; } // Returnerer den maksimale værdi, som // kan lægges i en rygsæk med kapacitet W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vektor> K(n + 1, vektor (W + 1));  // Byg tabel K[][] nedefra og op for (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; } // Returnerer den maksimale værdi, som // kan lægges i en rygsæk med kapacitet W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Byg tabel K[][] nedefra og op for (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; } // Returnerer den maksimale værdi, der kan // sættes i en rygsæk med kapacitet W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = ny int[n + 1][W + 1];  // Byg tabel K[][] nedefra og op for (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; } // Returnerer den maksimale værdi, som // kan lægges i en rygsæk af // kapacitet W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = ny int[n + 1, W + 1];  // Byg tabel K[][] i bund // op måde for (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;  } // Returnerer den maksimale værdi, der kan // sættes i en rygsæk med kapacitet W funktion knapSæk(W, wt, val, n) { lad i, w;  lad K = ny Array(n + 1);    // Byg tabel K[][] nedefra og op for (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. ?>>
   
  Produktion      Tidskompleksitet:    O(N * W). hvor 'N' er antallet af elementer og 'W' er kapacitet.  
    Hjælpeplads:    O(N * W). Brugen af et 2-D-array af størrelse 'N*W'.
c struktur i struktur
     Pladsoptimeret tilgang til 0/1 knapsæk-problem ved hjælp af dynamisk programmering:    
Følg nedenstående idé for at løse problemet:
  For at beregne den aktuelle række i dp[]-arrayet kræver vi kun forrige række, men hvis vi begynder at krydse rækkerne fra højre mod venstre, kan det kun gøres med en enkelt række
 
Nedenfor er implementeringen af ovenstående tilgang:
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--) { 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 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--) { if (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--) { if (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--) { if (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>
   
  Produktion  220>
     Tidskompleksitet    : O(N * W). Da overflødige beregninger af tilstande undgås  
    Hjælpeplads    : O(W) Da vi bruger et 1-D-array i stedet for et 2-D-array

TechCodeview

Rekursionstilgang til 0/1 rygsækproblem:

Dynamisk programmeringstilgang til 0/1 knapsækproblem

Memoiseringsmetode for 0/1 knapsækproblem:

Bottom-up tilgang til 0/1 Rullesæk-problem:

Pladsoptimeret tilgang til 0/1 knapsæk-problem ved hjælp af dynamisk programmering:

vægt⇢ vare⇣/	1	2	3	4	5	6
0	0	0	0	0	0	0
1	10	10	10	10	10	10
2	10	femten	25	25	25	25
3	10	femten	40	halvtreds	55	65