前提条件: ナップサック問題の概要、その種類と解決方法
与えられた N 各アイテムにある程度の重さと利益が関連付けられており、容量のあるバッグも与えられているアイテム で 、[つまり、バッグには最大で次のものを収納できます。 で その中に重量がある]。タスクは、アイテムに関連する利益の合計が可能な限り最大になるようにアイテムをバッグに入れることです。
注記： ここでの制約は、アイテムを完全にバッグに入れることができるか、まったく入れられないかのどちらかである[アイテムの一部をバッグに入れることは不可能]です。
例:
推奨練習問題 0 – 1 ナップザック問題 試してみましょう!入力： N = 3、W = 4、利益[] = {1, 2, 3}、重み[] = {4, 5, 1}
出力： 3
説明： 重みが 4 以下の項目が 2 つあります。重み 4 の項目を選択した場合、考えられる利益は 1 です。重み 1 の項目を選択した場合、考えられる利益は 3 です。したがって、考えられる最大利益はバッグの容量は4のため、重さ4と重さ1のアイテムを一緒に入れることはできませんのでご注意ください。
入力： N = 3、W = 3、利益[] = {1, 2, 3}、重み[] = {4, 5, 6}
出力： 0
0/1 ナップサック問題に対する再帰アプローチ:
この問題を解決するには、次のアイデアに従ってください。
簡単な解決策は、アイテムのすべてのサブセットを考慮し、すべてのサブセットの合計重量と利益を計算することです。合計の重みが W より小さいサブセットのみを考慮します。そのようなすべてのサブセットから、最大の利益を持つサブセットを選択します。
Spring Boot の注釈最適な下部構造 : アイテムのすべてのサブセットを考慮するには、各アイテムに対して 2 つのケースが考えられます。
- ケース 1: 項目は最適なサブセットに含まれています。
- ケース 2: この商品は最適セットには含まれておりません。
問題を解決するには、次の手順に従ってください。
N 個の項目から取得される最大値は、次の 2 つの値の最大値となります。
- ケース 1 (N を含む)番目item): Nの値番目アイテムに、残りの N-1 個のアイテムと残りの重みから得られる最大値を加えた値、つまり (N 個の W 重み)番目アイテム）。
- ケース 2 (N を除く)番目item)：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>b)? a:b; } // 容量 W int knapSack(int W, int wt[], int val[], int n) // 基本ケース if (n == 0 //) のナップザックに入れることができる最大値を返します。ドライバーコード int main() { int 利益 [] = { 60, 100, 120 }; int 重み [] = { 10, 20, 30 }; int n = sizeof(利益) / sizeof( 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>b)? 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); // 最大の 2 つのケースを返します: // (1) n 番目の項目が含まれている // (2) 含まれていない場合 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 }; int 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>b)? a:b; } // // 容量 W のナップザックに入れることができる最大値を返します static int knapSack(int W, int wt[], int val[], int n) // ドライバー コード public static void main(文字列 args[]) { intprofit[] = new int[] { 60, 100, 120 }; int 重み[] = 新しい int[] { 10, 20, 30 }; int 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) # 2 つのケースの最大値を返します: # (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 によって寄稿されました>>
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; } // 容量 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); // 最大の 2 つのケースを返します: // (1) n 番目の項目が含まれる // (2) 含まれない場合 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 }; int W = 50; int n = 利益.長さ; Console.WriteLine(knapSack(W, 重量, 利益, n)); } } // このコードは Sam007 によって提供されました>>'JavaScript$W) return knapSack($W, $wt, $val, $n - 1); // 最大 2 つのケースを返します: // (1) n 番目の項目が含まれています // (2) 含まれていない場合 return max($val[$n - 1] + knapSack($W - $wt[$n - 1] 、$wt、$val、$n - 1)、knapSack($W、$wt、$val、$n-1)); // ドライバーコード $profit = array(60, 100, 120); $weight = 配列(10, 20, 30); $W = 50; $n = カウント($profit); echo knapSack($W, $weight, $profit, $n); // このコードは Sam007 によって提供されました ?>>> 出力
220>
時間計算量: O(2N)
補助スペース: O(N)、再帰に必要なスタック領域
0/1 ナップザック問題に対する動的計画法によるアプローチ
0/1 ナップザック問題に対するメモ化アプローチ:
注記： 再帰を使用する上記の関数は、同じ部分問題を何度も計算することに注意してください。次の再帰ツリーを参照してください。K(1, 1) は 2 回評価されています。
次の再帰ツリーでは、 K() knapSack() を指します。次の再帰ツリーに示されている 2 つのパラメーターは、n と W です。
再帰ツリーは次のサンプル入力用です。
重み[] = {1, 1, 1}、W = 2、利益[] = {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 個と 1 単位重量のアイテム 3 個の再帰ツリー。
同じ部分問題が何度も繰り返されるため、問題を解決するために次のアイデアを実装できます。
初めて部分問題が発生した場合は、特定の状態 (n, w) を格納できる 2 次元配列を作成することで、この問題を解決できます。同じ状態 (n, w) に再び遭遇した場合、指数関数的に計算する代わりに、定数時間でテーブルに保存された結果を直接返すことができます。
dateformat.format 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); dp[インデックス][W]を返します; } else { // return 前に値をテーブルに格納 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]; // テーブルを動的に作成するループ 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>b)? a:b; } // 最大利益の値を返します 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> パイソン # 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__':profit = [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 によって提供されています>'>C# // A utility function that returns // maximum of two integers function max(a, b) { return (a>b)? a:b; } // 最大利益の値を返す 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) ); 戻り knapSackRec(W, wt, val, N, dp); var 利益 = [ 10, 20, 30 ]; var N = 利益; console.log(knapSack(W, 重量, 利益, N)); // このコードは akshitsaxenaa09 によって提供されました。
出力 220>
時間計算量: O(N * W)。状態の冗長な計算が回避されるため。
補助スペース: O(N * W) + O(N)。中間状態を保存するために 2D 配列データ構造を使用し、再帰スタックには O(N) 補助スタック スペース (ASS) が使用されています。
0/1 ナップザック問題に対するボトムアップ アプローチ:
この問題を解決するには、次のアイデアに従ってください。
部分問題が再度評価されるため、この問題には重複する部分問題のプロパティがあります。したがって、0/1 ナップザック問題には両方の特性があります (「 これ そして これ ) 動的計画法の問題。他の典型的なものと同じように 動的プログラミング(DP)の問題 同様に、ボトムアップ方式で一時配列 K[][] を構築することで、同じ部分問題の再計算を回避できます。
図：
以下に上記のアプローチを図示します。
させて、 重量[] = {1, 2, 3}、利益[] = {10, 15, 40}、容量 = 6
- どの要素も満たされていない場合、考えられる利益は 0 です。
体重⇢
アイテム⇣/0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 2 3
- バッグに最初のアイテムを入れる場合: 上記の手順に従うと、表は次のようになります。
体重⇢
アイテム⇣/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
- 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 3 4 5 6 0 0 0 0 0 0 0 0 1 0 10 10 10 10 10 10 2 0 10 15 25 25 25 25 3
- 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 です。
体重⇢
アイテム⇣/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 15 25 25 25 25 3 0 10 15 40 50 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>b)? a:b; } // 容量 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>b)? a:b; } // 容量 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; }> ジャワ // 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; } // 容量 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 */> パイソン # 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; } // 容量 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> 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; } // 容量 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」の 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>
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) 2 次元配列の代わりに 1 次元配列を使用しているため