/* 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; } // Returnerar det maximala värdet som // kan läggas i en ryggsäck med kapacitet W int knapSack(int W, int wt[], int val[], int n) // Base Case if (n == 0 // Drivrutinskod int main() { int profit[] = { 60, 100, 120 } = { 10, 20, 30 } int W = 50 n = 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; } // Returnerar det maximala värdet som kan // läggas i en ryggsäck med kapacitet W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Om vikten av det n:e föremålet är mer än // Ryggsäckens kapacitet W, kan detta föremål inte // inkluderas i den optimala lösningen om (wt[n - 1]> W) return knapSack(W, wt, val, n -1);  // Returnera maximalt två fall: // (1) n:te objektet ingår // (2) inte inkluderat annars returnera max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n-1), ryggsäck (W, wt, val, n-1));  // Drivrutinskod int main() { int profit[] = { 60, 100, 120 };  int vikt[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', knapSack(W, vikt, vinst, n));  returnera 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; } // Returnerar det maximala värdet som // kan läggas i en ryggsäck av // 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 vikt[] = ny int[] { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.println(knapSack(W, vikt, vinst, n));  } } /*Denna kod är bidragit av 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): returnera ryggsäck(W, wt, val, n-1) # returnera max två fall: # (1) n:te artikeln ingår # (2) ingår inte annars: return max( val[n-1] + ryggsäck ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # end of function backSack # Driver Code if __name__ == '__main__': profit = [60, 100, 120] vikt = [10, 20, 30] W = 50 n = len(profit) print ryggsäck(W, vikt, vinst, n) # Denna kod är bidragit av 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; } // Returnerar det maximala värdet som kan // läggas i en ryggsäck med kapacitet W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Om vikten av det n:e föremålet är // mer än Ryggsäckens kapacitet W, // kan detta föremål inte // inkluderas i den optimala lösningen om (wt[n - 1]> W) return knapSack(W, wt, val n-1);  // Returnera maximalt två fall: // (1) n:te objektet ingår // (2) inte inkluderat annars returnera max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n-1), ryggsäck (W, wt, val, n-1));    // Driver code public static void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] vikt = ny int[] { 10, 20, 30 };  int W = 50;  int n = vinst.Längd;  Console.WriteLine(knapSack(W, vikt, vinst, n));  } } // Denna kod är bidragit från 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;  } // Returnerar det maximala värdet som kan // läggas i en ryggsäck med kapacitet W funktion ryggSäck(W, wt, val, n) // Base Case if (n == 0 let profit = [ 60, 100, 120 ] ; låt vikt = [ 10, 20, 30 ];PHP220>

Tidskomplexitet: O(2^N)
Hjälputrymme: O(N), Stackutrymme krävs för rekursion

Dynamisk programmeringsmetod för 0/1 Knapsack Problem

Memoiseringsmetod för 0/1 Knapsack-problem:

Notera: Det bör noteras att ovanstående funktion som använder rekursion beräknar samma delproblem om och om igen. Se följande rekursionsträd, K(1, 1) utvärderas två gånger.

I följande rekursionsträd, K() hänvisar till knapSack(). De två parametrarna som anges i följande rekursionsträd är n och W.
Rekursionsträdet är till för följande exempelingångar.
vikt[] = {1, 1, 1}, W = 2, vinst[] = {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äd för ryggsäckskapacitet 2 enheter och 3 artiklar med 1 viktenhet.

Eftersom det finns upprepningar av samma delproblem om och om igen kan vi implementera följande idé för att lösa problemet.

Om vi ​​får ett delproblem första gången kan vi lösa detta problem genom att skapa en 2D-array som kan lagra ett visst tillstånd (n, w). Om vi ​​nu stöter på samma tillstånd (n, w) igen istället för att beräkna det i exponentiell komplexitet kan vi direkt returnera dess resultat lagrat i tabellen i konstant tid.

java xor

Nedan är implementeringen av ovanstående tillvägagångssätt:

// 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) { // Lagra värdet av funktionsanrop // stack i tabell före retur dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  return dp[index][W];  } else { // Lagra värde i en tabell före retur dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , vikt, val, index - 1, dp));  // Returneringsvärde för tabellen efter lagring av retur dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // dubbelpekare för att deklarera //-tabellen dynamiskt int** dp;  dp = ny int*[n];  // loop för att skapa tabellen dynamiskt för (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; } // Returnerar värdet av maximal vinst statisk int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) returnera dp[n][W];  if (wt[n - 1]> W) // Lagra värdet av funktionsanrop // stack i tabell före returretur dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Returnera tabellens värde efter lagring av retur 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) { // Deklarera tabellen dynamiskt int dp[][] = new int[N + 1][W + 1];  // Loop för att initialt fylla //-tabellen med -1 för (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] = ryggsäck(wt, val, W, n-1) return t[n][W] # Förarkod om __namn__ == '__main__': vinst = [60, 100, 120] vikt = [10, 20, 30] W = 50 n = len(profit) # Vi initialiserar matrisen med -1 först. t = [[-1 för i i intervallet(W + 1)] för j i intervallet(n + 1)] print(knapsäck(vikt, vinst, W, n)) # Denna kod är bidragit av Prosun Kumar Sarkar>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b) ? a:b;  } // Returnerar värdet för funktionen för maximal vinst knapSackRec(W, wt, val, n,dp) // Basvillkor if (n == 0 function knapSack( W, wt,val,N) { // Deklarera dp-tabellen dynamiskt // Initialisering av dp-tabeller (rad och kolumn) 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 ]; var vikt = [ var W = 50; ; console.log(knapSack(W, vikt, profit, N));  
  Produktion  
220>
  
    Tidskomplexitet:    O(N * W). Då överflödiga beräkningar av tillstånd undviks.  
    Hjälputrymme:    O(N * W) + O(N). Användningen av en 2D-matrisdatastruktur för lagring av mellantillstånd och O(N) extra stackutrymme (ASS) har använts för rekursionsstack
 
    Bottom-up-metoden för 0/1 säckproblem:    
Följ idén nedan för att lösa problemet:
  
Eftersom underproblem utvärderas igen, har detta problem egenskapen Överlappande underproblem. Så 0/1 Knapsack-problemet har båda egenskaperna (se detta och detta ) av ett dynamiskt programmeringsproblem. Som andra typiska Dynamisk programmering (DP) problem , kan omräkning av samma delproblem undvikas genom att konstruera en temporär array K[][] på ett nedifrån-och-upp-sätt.
 
    Illustration:    
 
Nedan är illustrationen av ovanstående tillvägagångssätt:
  
Låta,    vikt[] = {1, 2, 3}, vinst[] = {10, 15, 40}, Kapacitet = 6    
 
Om inget element är ifyllt är den möjliga vinsten 0.
vikt⇢  
artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    För att fylla det första föremålet i påsen:    Om vi ​​följer ovannämnda procedur kommer tabellen att se ut som följande.
vikt⇢  
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
 
 
 
 
 
 
 
    För att fylla den andra posten:       
När jthWeight = 2 är den maximala möjliga vinsten max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
När jthWeight = 3, då är den maximala möjliga vinsten max(2 läggs inte, 2 läggs i påsen) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
vikt⇢  
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
femton
25
25
25
25
3
 
 
 
 
 
 
 
    För att fylla den tredje posten:     
När jthWeight = 3 är den maximala möjliga vinsten max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
När jthWeight = 4 är den maximala möjliga vinsten max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
När jthWeight = 5 är den maximala möjliga vinsten max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
När jthWeight = 6 är den maximala möjliga vinsten max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
vikt⇢  
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
femton
25
25
25
25
3
0
10
femton
40
femtio
55
65
Nedan är implementeringen av ovanstående tillvägagångssätt:
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; } // Returnerar det maximala värdet som // kan läggas i en ryggsäck med kapacitet W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vektor> K(n + 1, vektor (W+1));  // Bygg tabell K[][] nedifrån och upp för (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; } // Returnerar det maximala värdet som // kan läggas i en ryggsäck med kapacitet W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Bygg tabell K[][] nedifrån och upp för (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; } // Returnerar det maximala värdet som kan // läggas i en ryggsäck 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];  // Bygg tabell K[][] nedifrån och upp för (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 */>
 Pytonorm 
# 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; } // Returnerar det maximala värdet som // kan läggas i en ryggsäck 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];  // Bygg tabell K[][] i botten // uppåt för (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;  } // Returnerar det maximala värdet som kan // läggas i en ryggsäck med kapacitet W function knapSack(W, wt, val, n) { let i, w;  låt K = ny Array(n + 1);    // Bygg tabell K[][] nedifrån och upp för (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      Tidskomplexitet:    O(N * W). där 'N' är antalet element och 'W' är kapacitet.  
    Hjälputrymme:    O(N * W). Användningen av en 2D-matris med storleken 'N*W'.
fmovies Indien
 
    Utrymmesoptimerad tillvägagångssätt för 0/1 Knapsack-problem med dynamisk programmering:    
Följ idén nedan för att lösa problemet:
  
För att beräkna den aktuella raden i dp[]-matrisen kräver vi bara föregående rad, men om vi börjar korsa raderna från höger till vänster så kan det göras med endast en enda rad
 
Nedan är implementeringen av ovanstående tillvägagångssätt:
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>
 Pytonorm 
# 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>
 
    Tidskomplexitet    : O(N * W). Då överflödiga beräkningar av tillstånd undviks  
    Hjälputrymme    : O(W) Eftersom vi använder en 1-D array istället för en 2-D array