/* 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>비) ? a : b; } // // 용량이 있는 배낭에 넣을 수 있는 최대값을 반환합니다. W int knapSack(int W, int wt[], int val[], int n) // 기본 사례 if (n == 0 // 드라이버 코드 int main() { int 이익[] = { 60, 100, 120 }; int Weight[] = { 10, 20, 30 } int n = sizeof(이익) / sizeof(이익) 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>비) ? a : b; } // // 용량의 배낭에 넣을 수 있는 최대값을 반환합니다. 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), knapSack(W, wt, val, n - 1));  // 드라이버 코드 int main() { intprofit[] = { 60, 100, 120 };  int 가중치[] = { 10, 20, 30 };  정수 W = 50;  int n = sizeof(이익) / sizeof(이익[0]);  printf('%d', knapSack(W, 무게, 이익, n));  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>비) ? a : b; } // // 용량이 W인 배낭에 // 넣을 수 있는 최대값을 반환합니다. static int knapSack(int W, int wt[], int val[], int n) // 드라이버 코드 public static void main( String args[]) { int 이익[] = new int[] { 60, 100, 120 };  int 가중치[] = new int[] { 10, 20, 30 };  정수 W = 50;  int n = 이익.길이;  System.out.println(knapSack(W, 무게, 이익, n));  } } /*이 코드는 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): 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), knapSack(W, wt, val, n-1)) # 함수 끝 knapSack # 드라이버 코드 if __name__ == '__main__': 이익 = [60, 100, 120] 가중치 = [10, 20, 30] W = 50 n = len(이익) print knapSack(W, 가중치, 이익, n) # 이 코드는 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>비) ? a : b; } // // 용량이 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 return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));    // 드라이버 코드 public static void Main() { int[]profit = new int[] { 60, 100, 120 };  int[] 가중치 = 새로운 int[] { 10, 20, 30 };  정수 W = 50;  int n = 이익.길이;  Console.WriteLine(knapSack(W, 무게, 이익, 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>비) ? a : b;  } // // 용량의 배낭에 넣을 수 있는 최대값을 반환합니다. W function knapSack(W, wt, val, n) // 기본 사례 if (n == 0 letprofit = [ 60, 100, 120 ] ; 가중치 = [ 10, 20, 30 ]; 하자 n = 이익.log(knapSack(W, 가중치, 이익, n));PHP220>

시간 복잡도: 오(2^N)
보조 공간: O(N), 재귀에 필요한 스택 공간

0/1 배낭 문제에 대한 동적 프로그래밍 접근법

0/1 배낭 문제에 대한 메모 접근 방식:

메모: 재귀를 사용하는 위 함수는 동일한 하위 문제를 계속해서 계산한다는 점에 유의해야 합니다. 다음 재귀 트리를 참조하세요. K(1, 1)은 두 번 평가됩니다.

다음 재귀 트리에서, 케이() knapSack()을 참조합니다. 다음 재귀 트리에 표시된 두 매개변수는 n과 W입니다.
재귀 트리는 다음 샘플 입력을 위한 것입니다.
가중치[] = {1, 1, 1}, W = 2, 이익[] = {10, 20, 30}

케이(3, 2)
/
/
케이(2, 2) 케이(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개 단위이고 단위 중량이 1개인 항목 3개에 대한 재귀 트리입니다.

동일한 하위 문제가 계속해서 반복되므로 문제를 해결하기 위해 다음 아이디어를 구현할 수 있습니다.

처음으로 하위 문제가 발생하면 특정 상태(n, w)를 저장할 수 있는 2차원 배열을 만들어 이 문제를 해결할 수 있습니다. 이제 동일한 상태(n, w)를 다시 발견하면 지수 복잡도로 계산하는 대신 상수 시간에 테이블에 저장된 결과를 직접 반환할 수 있습니다.

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) { // 함수 호출의 값을 // 테이블에 저장하고 return 전에 dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  dp[인덱스][W]를 반환합니다.  } else { // return 전에 테이블에 값 저장 dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , wt, val, index - 1, dp));  // 저장 후 테이블의 반환값 return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // 테이블을 동적으로 선언하기 위한 // 이중 포인터 int** dp;  dp = 새로운 int*[n];  // 동적으로 테이블을 생성하는 루프 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; }>

// 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>비) ? a : b; } // 최대 이익 값을 반환합니다. static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) return 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>

# 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] = knapsack(wt, val, W, n-1) return t[n][W] # 드라이버 코드 if __name__ == '__main__': 이익 = [60, 100, 120] Weight = [10, 20, 30] W = 50 n = len(profit) # 처음에는 -1로 행렬을 초기화합니다. t = [[-1 for i in range(W + 1)] for j in range(n + 1)] print(knapsack(weight,profit,W,n)) # 이 코드는 Prosun Kumar Sarkar가 기여했습니다>'>씨# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>비) ? a : b;  } // 최대 이익 값을 반환 function knapSackRec(W, wt, val, n,dp) // 기본 조건 if (n == 0 function knapSack( W, wt,val,N) { // dp 테이블 선언 동적으로 // 아래 -1로 dp 테이블(행 및 열) 초기화 var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); return knapSackRec(W, wt, val, N, dp) } var 이익= [ 60, 100, 120 ]; var Weight = [ 10, 20, 30 ]; ; console.log(knapSack(W, Weight,profit,N)); // 이 코드는 akshitsaxenaa09에서 제공한 것입니다.  
  산출  
220>
  
    시간 복잡도:    O(N*W). 상태에 대한 중복 계산이 방지됩니다.  
    보조 공간:    O(N * W) + O(N). 재귀 스택에는 중간 상태 저장을 위한 2차원 배열 데이터 구조와 O(N) 보조 스택 공간(ASS)을 사용했습니다.
 
    0/1 배낭 문제에 대한 상향식 접근 방식:    
문제를 해결하려면 아래 아이디어를 따르십시오.
  
하위 문제가 다시 평가되므로 이 문제에는 Overlapping Sub-problems 속성이 있습니다. 따라서 0/1 배낭 문제에는 두 가지 속성이 모두 있습니다(참조: 이것 그리고 이것 ) 동적 프로그래밍 문제. 다른 전형적인 것처럼 동적 프로그래밍(DP) 문제 , 상향식 방식으로 임시 배열 K[][]를 구성하면 동일한 하위 문제의 재계산을 피할 수 있습니다.
 
    삽화:    
피트 데이비슨
 
다음은 위의 접근 방식을 보여줍니다.
  
허락하다,    무게[] = {1, 2, 3}, 이익[] = {10, 15, 40}, 용량 = 6    
 
요소가 채워지지 않으면 가능한 이익은 0입니다.
무게⇢  
아이템⇣/
0
1
2
삼
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
삼
 
 
 
 
 
 
 
    가방의 첫 번째 품목을 채우려면:    위에서 언급한 절차를 따르면 테이블은 다음과 같습니다.
무게⇢  
아이템⇣/
0
1
2
삼
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
 
 
 
 
 
 
 
삼
 
 
 
 
 
 
 
    두 번째 항목을 채우려면:       
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.
무게⇢  
아이템⇣/
0
1
2
삼
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
0
10
열 다섯
25
25
25
25
삼
 
 
 
 
 
 
 
    세 번째 항목을 채우려면:     
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입니다.
무게⇢  
아이템⇣/
0
1
2
삼
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
0
10
열 다섯
25
25
25
25
삼
0
10
열 다섯
40
오십
55
65
다음은 위의 접근 방식을 구현한 것입니다.
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>비) ? a : b; } // // 용량의 배낭에 넣을 수 있는 최대값을 반환합니다. W int knapSack(int W, int wt[], int val[], int n) { int i, w;  벡터> K(n + 1, 벡터 (W + 1));  // (i = 0; i에 대해 상향식으로 테이블 K[][] 구축<= 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>
 씨 
// 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>비) ? a : b; } // // 용량의 배낭에 넣을 수 있는 최대값을 반환합니다. W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // (i = 0; i에 대해 상향식으로 테이블 K[][]를 구축합니다.<= 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; }>
 자바 
// 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>비) ? a : b; } // // 용량이 W인 배낭에 넣을 수 있는 최대값을 반환합니다. static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = 새로운 int[n + 1][W + 1];  // (i = 0; i에 대해 상향식으로 테이블 K[][]를 구축합니다.<= 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 */>
 파이썬 
# 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>
 씨# 
// 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>비) ? a : b; } // // 용량이 W인 배낭에 // 넣을 수 있는 최대값을 반환합니다. static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = 새로운 int[n + 1, W + 1];  // 테이블 K[][]를 아래쪽으로 // 위쪽으로 구성 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>
 자바스크립트 
 // 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>비) ? a : b;  } // W 용량의 배낭에 // 넣을 수 있는 최대값을 반환 function knapSack(W, wt, val, n) { let i, w;  K = 새로운 배열(n + 1)이라고 하자;    // (i = 0; i에 대해 상향식으로 테이블 K[][]를 구축합니다.<= 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). 'N*W' 크기의 2차원 배열을 사용합니다.
 
    동적 프로그래밍을 사용한 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 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 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>
 씨# 
// 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>
 자바스크립트 
 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) 2차원 배열 대신 1차원 배열을 사용하므로