logo

TechCodeview

0/1 Проблема з ранцем

Передумови: Знайомство з проблемою ранця, її видами та способами їх вирішення

Дано Н предмети, де кожен предмет має певну вагу та пов’язаний з ним прибуток, а також дається мішок із місткістю IN , [тобто сумка може вмістити максимум IN вага в ньому]. Завдання полягає в тому, щоб покласти предмети в мішок так, щоб сума пов'язаних з ними прибутків була максимально можливою.

Примітка: Обмеження тут полягає в тому, що ми можемо або повністю помістити предмет у сумку, або не можемо помістити його взагалі [Неможливо помістити частину предмета в сумку].



приклади:

введення: N = 3, W = 4, прибуток [] = {1, 2, 3}, вага [] = {4, 5, 1}
Вихід: 3
Пояснення: Є два предмети, які мають вагу менше або дорівнює 4. Якщо ми вибираємо предмет з вагою 4, можливий прибуток дорівнює 1. А якщо ми вибираємо предмет з вагою 1, можливий прибуток дорівнює 3. Отже, максимально можливий прибуток дорівнює 3. Зверніть увагу, що ми не можемо об’єднати предмети з вагою 4 і 1 разом, оскільки місткість мішка дорівнює 4.

введення: N = 3, W = 3, прибуток [] = {1, 2, 3}, вага [] = {4, 5, 6}
Вихід: 0

Рекомендована практика 0 – 1 Проблема з рюкзаком Спробуйте!

Рекурсивний підхід для проблеми ранця 0/1:

Щоб вирішити проблему, дотримуйтеся наведеної нижче ідеї:

Просте рішення полягає в тому, щоб розглянути всі підмножини елементів і обчислити загальну вагу та прибуток усіх підмножин. Розглянемо лише ті підмножини, загальна вага яких менша за W. З усіх таких підмножин виберіть підмножину з максимальним прибутком.

робити в java

Оптимальна підструктура : Щоб розглянути всі підмножини елементів, для кожного елемента може бути два випадки.

  • Випадок 1: Елемент входить до оптимальної підмножини.
  • Випадок 2: Товар не входить в оптимальний комплект.

Щоб вирішити проблему, виконайте наведені нижче дії.

Максимальне значення, отримане з «N» елементів, є максимальним із наступних двох значень.

  • Випадок 1 (включно з Nтиспункт): Значення нтиселемент плюс максимальне значення, отримане за допомогою решти N-1 елементів і залишкової ваги, тобто (W-вага Nтиспункт).
  • Випадок 2 (виключити Nтиселемент): Максимальне значення, отримане за допомогою N-1 елементів і ваги W.
  • Якщо вага «Nтис«елемент більший за «W», то N-й елемент не може бути включений і Випадок 2 це єдина можливість.

Нижче наведено реалізацію вищезазначеного підходу:

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>б) ? а : б; } // Повертає максимальне значення, // яке можна помістити в рюкзак місткістю W int knapSack(int W, int wt[], int val[], int n) // Базовий випадок if (n == 0 // Код драйвера int main() { int profit[] = { 10, 20, 30 }; int n = sizeof(profit) / sizeof(profit[); 0]);<< knapSack(W, weight, profit, n);  return 0; } // This code is contributed by rathbhupendra>
C 
/* 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>б) ? а : б; } // Повертає максимальне значення, яке можна // покласти в рюкзак місткістю W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Якщо вага n-го предмета перевищує // місткість рюкзака W, то цей предмет // не можна включити в оптимальне рішення if (wt[n - 1]> W) return knapSack(W, wt, val, n) - 1);  // Повертає максимум із двох випадків: // (1) n-й елемент включено // (2) не включено else return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), ранець (W, wt, val, n - 1));  // Код драйвера int main() { int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(прибуток) / sizeof(прибуток[0]);  printf('%d', ранець(W, вага, прибуток, n));  повернути 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>б) ? а : б; } // Повертає максимальне значення, яке // можна помістити в рюкзак // місткістю W static int knapSack(int W, int wt[], int val[], int n) // Код драйвера 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));  } } /*Цей код створено Раджатом Мішрою */>
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): повертає knapSack(W, wt, val, n-1) # повертає максимум двох випадків: # (1) n-й елемент включено # (2) не включено ще: return max( val[n-1] + knapSack ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # кінець функції knapSack # Код драйвера, якщо __name__ == '__main__': прибуток = [60, 100, 120] вага = [10, 20, 30] W = 50 n = len(прибуток) print knapSack(W, вага, прибуток, n) # Цей код надав Нікіл Кумар Сінгх>
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>б) ? а : б; } // Повертає максимальне значення, яке // можна покласти в рюкзак місткістю W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Якщо вага n-го предмета // перевищує місткість рюкзака W, // цей предмет не можна // включити до оптимального рішення if (wt[n - 1]> W) return knapSack(W, wt, val , n - 1);  // Повертає максимум із двох випадків: // (1) n-й елемент включено // (2) не включено else повертає max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), ранець (W, wt, val, n - 1));    // Код драйвера public 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));  } } // Цей код створено Sam007>>>Javascript$W) повернути ранець($W, $wt, $val, $n - 1); // Повертає максимум із двох випадків: // (1) n-й елемент включено // (2) не включено else return max($val[$n - 1] + knapSack($W - $wt[$n - 1]) , $wt, $val, $n - 1), ранець($W, $wt, $val, $n-1));  // Код драйвера $profit = array(60, 100, 120); $weight = array(10, 20, 30); $W = 50; $n = count($profit); echo рюкзак ($W, $weight, $profit, $n); // Цей код створено Sam007 ?>>
Вихід 
220>

Часова складність: O(2Н)
Допоміжний простір: O(N), простір у стеку, необхідний для рекурсії

Підхід динамічного програмування для задачі ранця 0/1

Підхід запам'ятовування для проблеми ранця 0/1:

Примітка: Слід зазначити, що наведена вище функція за допомогою рекурсії обчислює ті самі підпроблеми знову і знову. Перегляньте наступне дерево рекурсії, K(1, 1) обчислюється двічі.

У наступному дереві рекурсії К() посилається на knapSack(). У наступному дереві рекурсії вказані два параметри: n і W.
Дерево рекурсії призначене для наступних зразків вхідних даних.
weight[] = {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)

Дерево рекурсії для ємності рюкзака 2 одиниці та 3 предмети по 1 одиниці ваги.

Оскільки одна і та ж підпроблема повторюється знову і знову, ми можемо застосувати наступну ідею для вирішення проблеми.

Якщо ми отримуємо підпроблему вперше, ми можемо вирішити цю проблему, створивши 2-D масив, який може зберігати певний стан (n, w). Тепер, якщо ми знову зустрінемо той самий стан (n, w), замість того, щоб обчислювати його в експоненціальній складності, ми можемо безпосередньо повернути його результат, який зберігається в таблиці в постійному часі.

concat рядок Java

Нижче наведено реалізацію вищезазначеного підходу:

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) { // Зберігати значення виклику функції // стек у таблиці перед поверненням dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  return dp[index][W];  } else { // Зберігати значення в таблиці перед поверненням dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , wt, val, індекс - 1, dp));  // Повернене значення таблиці після збереження return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // подвійний вказівник для // динамічного оголошення таблиці int** dp;  dp = новий int*[n];  // цикл для динамічного створення таблиці для (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>б) ? а : б; } // Повертає значення максимального прибутку static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) повертає 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];  // Цикл для початкового заповнення // таблиці значенням -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] = рюкзак(wt, val, W, n-1) return t[n][W] # Код водія if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) # Ми спочатку ініціалізуємо матрицю з -1. t = [[-1 для i в діапазоні (W + 1)] для j в діапазоні (n + 1)] print(knapsack(weight, profit, W, n)) # Цей код надав Просун Кумар Саркар>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>б) ? а : б;  } // Повертає значення максимального прибутку function knapSackRec(W, wt, val, n,dp) // Основна умова if (n == 0 function knapSack( W, wt,val,N) { // Оголошення таблиці dp динамічно // Ініціалізація таблиць dp (рядок і стовпці) з -1 нижче var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); return knapSack(W, wt, N, dp); var profit= [60, 20, 30]; var N = profit.length ; console.log(knapSack(W, weight, N)); // Цей код надано akshitsaxenaa09  
  Вихід  
220>
  
    Часова складність:    O(N * W). Оскільки зайві обчислення станів уникають.  
    Допоміжний простір:    O(N * W) + O(N). Використання структури даних 2D-масиву для зберігання проміжних станів і O(N) простору допоміжного стеку (ASS) використовувалося для стека рекурсії
 
    Підхід «знизу вгору» для проблеми ранця 0/1:    
Щоб вирішити проблему, дотримуйтеся наведеної нижче ідеї:
mylivericket

  
Оскільки підпроблеми оцінюються повторно, ця проблема має властивість Overlapping Sub-problems. Отже, проблема ранця 0/1 має обидві властивості (див це і це ) задачі динамічного програмування. Як і інші типові Проблеми динамічного програмування (DP). , повторного обчислення одних і тих самих підпроблем можна уникнути, побудувавши тимчасовий масив K[][] у спосіб знизу вгору.
 
    Ілюстрація:    
 
Нижче наведено ілюстрацію вищезазначеного підходу:
  
Дозволяти,    weight[] = {1, 2, 3}, profit[] = {10, 15, 40}, Capacity = 6    
 
  • Якщо жоден елемент не заповнений, то можливий прибуток дорівнює 0.
вага⇢  
пункт⇣/		0123456
00000000
1       
2       
3       
  •     Для заповнення першого предмета в мішку:    Якщо ми виконаємо описану вище процедуру, таблиця матиме такий вигляд.
вага⇢  
пункт⇣/		0123456
00000000
10101010101010
2       
3       
  •     Для заповнення другого пункту:       
    Коли jthWeight = 2, максимальний можливий прибуток дорівнює max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
    Коли jthWeight = 3, тоді максимально можливий прибуток дорівнює max(2 не покладено, 2 покладено в мішок) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
вага⇢  
пункт⇣/		0123456
00000000
10101010101010
2010п'ятнадцять25252525
3       
  •     Для заповнення третього пункту:     
    Коли jthWeight = 3, максимально можливий прибуток становить max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
    Коли jthWeight = 4, максимально можливий прибуток становить max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
    Коли jthWeight = 5, максимально можливий прибуток становить max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
    Коли jthWeight = 6, максимально можливий прибуток становить max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
вага⇢  
пункт⇣/		0123456
00000000
10101010101010
2010п'ятнадцять25252525
3010п'ятнадцять40п'ятдесят5565
Нижче наведено реалізацію вищезазначеного підходу:
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>б) ? а : б; } // Повертає максимальне значення, // яке можна помістити в рюкзак місткістю W int knapSack(int W, int wt[], int val[], int n) { int i, w;  вектор> K(n + 1, вектор (W + 1));  // Побудувати таблицю K[][] у спосіб знизу вгору для (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>б) ? а : б; } // Повертає максимальне значення, // яке можна помістити в рюкзак місткістю W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Побудувати таблицю K[][] у спосіб знизу вгору для (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>б) ? а : б; } // Повертає максимальне значення, яке // можна покласти в рюкзак місткістю W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = новий int[n + 1][W + 1];  // Побудувати таблицю K[][] у спосіб знизу вгору для (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>б) ? а : б; } // Повертає максимальне значення, // яке можна помістити в рюкзак // місткістю W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = новий int[n + 1, W + 1];  // Побудувати таблицю K[][] унизу // вгору для (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>б) ? а : б;  } // Повертає максимальне значення, // яке можна покласти в рюкзак місткістю W. function knapSack(W, wt, val, n) { let i, w;  нехай K = новий масив (n + 1);    // Побудувати таблицю K[][] у спосіб знизу вгору для (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. ?>>
   
  Вихід      Часова складність:    O(N * W). де «N» — кількість елементів, а «W» — ємність.  
    Допоміжний простір:    O(N * W). Використання 2-D масиву розміром «N*W».
 
    Оптимізований простір підхід для проблеми ранця 0/1 з використанням динамічного програмування:    
Щоб вирішити проблему, дотримуйтеся наведеної нижче ідеї:
  
Для обчислення поточного рядка масиву dp[] нам потрібен тільки попередній рядок, але якщо ми почнемо проходити рядки справа наліво, це можна зробити лише з одним рядком
 
Нижче наведено реалізацію вищезазначеного підходу:
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>
   
  Вихід  
220>
 
    Часова складність    : O(N * W). Оскільки зайві обчислення станів уникають  
    Допоміжний простір    : O(W) Оскільки ми використовуємо 1-D масив замість 2-D масиву