{"id":3398,"date":"2023-08-17T18:04:45","date_gmt":"2023-08-17T12:34:45","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3398"},"modified":"2023-08-17T18:04:47","modified_gmt":"2023-08-17T12:34:47","slug":"0-1-knapsack-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/0-1-knapsack-problem\/","title":{"rendered":"0-1 Knapsack Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#method-1-using-bruteforce-recursion\">Method 1 (Using Bruteforce Recursion):<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#method-2-using-dynamic-programming\">Method 2 (Using Dynamic Programming):<\/a><\/li><li><a href=\"#approach-1-using-memoization\">Approach 1: (Using memoization)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-using-iterative-dp\">Approach 2: (Using Iterative DP)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-3-space-optimized-solution\">Approach 3: (Space-optimized solution)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-can-we-solve-the-01-knapsack-problem-using-backtracking\">Q.1: Can we solve the 0\/1 Knapsack Problem using Backtracking?<\/a><\/li><li><a href=\"#q2-what-is-the-time-complexity-of-01-knapsack-problem\">Q.2: What is the Time Complexity of 0\/1 Knapsack Problem?<\/a><\/li><li><a href=\"#q3-can-we-solve-the-01-knapsack-problem-using-greedy-algorithm\">Q.3: Can we solve the 0\/1 Knapsack Problem using Greedy Algorithm?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a Knapsack\/Bag with W weight capacity and a list of N items with given v<sub>i<\/sub> value and w<sub>i<\/sub> weight. Put these items in the knapsack in order to maximise the value of all the placed items without exceeding the limit of the Knapsack.<\/p>\n\n\n\n<p><strong>0-1 Knapsack Problem<\/strong><\/p>\n\n\n\n<p>The problem remains the same but one cannot break the items you can either select it fully ( 1) or don\u2019t select it (0 ).<\/p>\n\n\n\n<p><strong>Example of 0-1 Knapsack :<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"748\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Example of 0-1 Knapsack\"  class=\"wp-image-3415 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack-300x219.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack-768x561.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack-380x278.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack-550x402.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-0-1-Knapsack-800x584.png 800w\" ><\/figure>\n\n\n\n<h2 id=\"method-1-using-bruteforce-recursion\">Method 1 (Using Bruteforce Recursion):<\/h2>\n\n\n\n<p>Our approach with recursion will be to try and create all the subsets of items with total weight less than that of the given capacity W. From the result we will return the subset with maximum value.&nbsp;<\/p>\n\n\n\n<p>For every element we can,<\/p>\n\n\n\n<ul><li>either select it or,&nbsp;<\/li><li>ignore and move forward.&nbsp;<\/li><\/ul>\n\n\n\n<p>If we select an item then its value will be added to our current value and weight will be subtracted from the current available space.&nbsp;<\/p>\n\n\n\n<p>Thus, if we take the maximum value out of both the calculated result for nth element i.e. result after selecting that element and after ignoring it, we can get to our desired answer.&nbsp;<\/p>\n\n\n\n<p><strong>Code for Above Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int knapsack01(int W,int N,vector&lt;int> &amp;v,vector&lt;int> &amp;w) {\n    \/* Base case 0 items left or knapsack is full *\/\n    if(N == 0 || W == 0) \n        return 0;\n    \/* if weight of current element is less than or equal to capacity we can \n    either include or exclude the item. *\/\n    if(w[N] &lt;= W){\n         return max(v[N]+knapsack01(W-w[N],N-1,v,w),knapsack01(W,N-1,v,w));\n    }\n    \/* if weight of current element is greater than the capacity we will\n    not include it thus returning just the ignoring part. *\/\n    return knapsack01(W,N-1,v,w);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ maximum Function for max of two integers    \nstatic int max(int a, int b) {    \n    if(a>b) return a;\n    else return b;\n}\n\nstatic int knapSack(int W,int N,int v[],int w[]) {\n    \/* Base case 0 items left or knapsack is full *\/\n    if(N == 0 || W == 0) \n        return 0;\n    \/* if weight of current element is less than or equal to capacity we can \n    either include or exclude the item. *\/\n    if(w[N] &lt;= W){\n         return max(v[N]+knapSack(W-w[N],N-1,v,w),knapSack(W,N-1,v,w));\n    }\n    \/* if weight of current element is greater than the capacity we will\n    not include it thus returning just the ignoring part. *\/\n    return knapSack(W,N-1,v,w);\n}\n<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def knapsack01(W,N,v,w):\n    # Base case 0 items left or knapsack is full \n    if N == 0 or W == 0:\n        return 0\n    # if weight of current element is less than or equal to capacity we can \n    # either include or exclude the item. \n    if w[N] &lt;= W:\n         return max(v[N]+knapsack01(W-w[N],N-1,v,w),knapsack01(W,N-1,v,w))\n    # if weight of current element is greater than the capacity we will\n    # not include it thus returning just the ignoring part. \n    else:\n    return knapsack01(W,N-1,v,w)\n<\/pre>\n\n\n\n<ul><li>Time Complexity of the above approach is O(2<sup>n<\/sup>).<\/li><\/ul>\n\n\n\n<h2 id=\"method-2-using-dynamic-programming\">Method 2 (Using Dynamic Programming):<\/h2>\n\n\n\n<p>In the above approach, we can observe that we are calling recursion for the same sub-problems again and again thus resulting in overlapping subproblems thus we can make use of Dynamic programming to solve the 0-1 Knapsack problem.\u00a0<\/p>\n\n\n\n<p><strong>For Example :<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"928\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dynamic programming to solve 0-1 Knapsack problem\"  class=\"wp-image-3416 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem-300x272.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem-768x696.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem-380x344.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem-550x498.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-programming-to-solve-0-1-Knapsack-problem-800x725.png 800w\" ><\/figure>\n\n\n\n<h2 id=\"approach-1-using-memoization\">Approach 1: (Using memoization)<\/h2>\n\n\n\n<p>In this approach, we\u2019ll store all the computed answers in a 2 dimensional Array with indices of items in rows and weights in columns and use it further for overlapping subproblems.<\/p>\n\n\n\n<p><br><strong>Code for Above Implementation<\/strong>:<\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-3\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int knapSackrecur(int W,int N,vector&lt;int> &amp;v,vector&lt;int> &amp;w,vector&lt;vector&lt;int>>&amp; dp){\n    \/* Base case 0 items left or knapsack is full *\/\n    if(N == 0 || W == 0) \n        return 0;\n\n    \/* Checking if the result exists in DP *\/\n\n    if(dp[N][W]!=-1) \n        return dp[N][W];\n    \n    \/* if weight of current element is less than or equal to capacity we can \n    either include or exclude the item and store it to DP. *\/\n    if(w[N] &lt;= W){\n         return dp[N][W] = max(v[N]+knapSackrecur(W-w[N],N-1,v,w,dp),knapSackrecur(W,N-1,v,w,dp));\n    }\n    \/* if weight of current element is greater than the capacity we will\n    not include it thus returning just the ignoring part and storing it to DP. *\/\n    return dp[N][W] = knapSackrecur(W,N-1,v,w,dp);\n}\nint knapsack01(int W,int N,vector&lt;int> &amp;v,vector&lt;int> &amp;w) {\n    \/\/ Defining Dp and initializing with -1.\n    vector&lt;vector&lt;int>> dp(N+1,vector&lt;int> (W+1,-1)); \n    return knapSackrecur(W,N-1,v,w,dp);\n}\n<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-3\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ maximum of two integers    \nstatic int max(int a, int b) {    \n    if(a>b) return a;\n    else return b;\n}\n\nstatic int knapSack(int W,int N,int v[],int w[],int [][]dp) {\n    \/* Base case 0 items left or knapsack is full *\/\n    if(N == 0 || W == 0) \n        return 0;\n\n    if(dp[N][W] == -1)\n        return dp[N][W];\n\n    \/* if weight of current element is less than or equal to capacity we can \n    either include or exclude the item. *\/\n    if(w[N] &lt;= W){\n         return dp[N][W] = max(v[N]+knapSack(W-w[N],N-1,v,w),knapSack(W,N-1,v,w));\n    }\n    \/* if weight of current element is greater than the capacity we will\n    not include it thus returning just the ignoring part. *\/\n    return dp[N][W] = knapSack(W,N-1,v,w);\n}\n\nstatic int knapsack01(int W,int N,int v[],int w[]){\n    \n    \/\/ Defining Dp and initializing with -1.\n    int DP[][] = new int [N+1][W+1];\n    for(int i=0;i&lt;=N;i++){\n        for(int j=0;j&lt;=W;j++){\n            DP[i][j] = -1;\n        }\n    }\n    return knapSack(W,N,v,w,DP);\n}\n<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-3\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Globally defining the DP and initialising as -1 \ndp = [[-1 for i in range(W+1)] for j in range(N+1)]\n\ndef knapSack(W,N,v,w):\n    # Base case 0 items left or knapsack is full \n    if N == 0 or W == 0:\n        return 0\n\n    # checking if the result is precalculated and returning it.\n    if dp[N][W] != -1:\n        return dp[N][W]\n\n    # if weight of current element is less than or equal to capacity we can \n    # either include or exclude the item. \n    if w[N] &lt;= W:\n         return dp[N][W] = max(v[N]+knapSack(W-w[N],N-1,v,w),knapSack(W,N-1,v,w))\n    # if weight of current element is greater than the capacity we will\n    # not include it thus returning just the ignoring part. \n    else:\n    return dp[N][W] = knapSack(W,N-1,v,w)\n<\/pre>\n\n\n\n<ul><li>Time Complexity of the above approach is O(N*W).<\/li><li>Space Complexity of the above approach is O(N*W).<\/li><\/ul>\n\n\n\n<h2 id=\"approach-2-using-iterative-dp\">Approach 2: (Using Iterative DP)<\/h2>\n\n\n\n<p>In this approach, we\u2019ll define 2 dimensional DP of the index for items defined on rows whereas weights from 1 to W on columns and for every weight we can compute the answer for placing items till the nth item. <\/p>\n\n\n\n<p>Similar to the recursive approach we can define two cases that are,\u00a0<\/p>\n\n\n\n<ul><li>Use this item or<\/li><li>Ignore it.<\/li><\/ul>\n\n\n\n<p>Thus for every, Dp[i][j] we can calculate values for these two cases and store out the maximum of those two,\u00a0<\/p>\n\n\n\n<p>Therefore we can get our answer for {i,j} as ,<\/p>\n\n\n\n<p>DP[i][j] = max(v[i] + DP[i-1][j-w[i]],DP[i-1][j])&nbsp;<\/p>\n\n\n\n<p><strong>Code for Above Implementation<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-4\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int knapsack01(int W,int N,vector&lt;int> &amp;v,vector&lt;int> &amp;w) {\n    int DP[N+1][W+1]; \/\/ Defining DP \n    \/* If there is no space left that is W reaches 0 then DP[i][0] \n    for every i will be 0.*\/\n    for(int i=0;i&lt;N+1;i++) DP[i][0] = 0;\n    \/* If there are no items left that is N reaches 0 then DP[0][i] \n    for every i will be 0.*\/\n    for(int i=0;i&lt;W+1;i++) DP[0][i] = 0;\n\n    for(int i=1;i&lt;N+1;i++){\n        for(int j=1;j&lt;W+1;j++){\n            if(w[i-1] &lt;= j){\n                \/* Taking max of both the cases i.e to take that \n                item or to ignore it.*\/\n                DP[i][j] = max(v[i-1]+DP[i-1][j-w[i-1]],DP[i-1][j]); \n            }\n            else{\n                \/* If the weight of current element is greater \n                than the space left in the bag we'll ignore it.*\/\n                DP[i][j] = DP[i-1][j];\n            }\n        }\n    }\n    \/* returning answer for W space and N items *\/\n    return DP[N][W]; }<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-4\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int knapSack(int W,int N,int v[],int w[]) {\n    int DP[][] = new int[N+1][W+1]; \/\/ Defining DP \n    \/* If there is no space left that is W reaches 0 then DP[i][0] \n    for every i will be 0.*\/\n    for(int i=0;i&lt;N+1;i++) DP[i][0] = 0;\n    \/* If there are no items left that is N reaches 0 then DP[0][i] \n    for every i will be 0.*\/\n    for(int i=0;i&lt;W+1;i++) DP[0][i] = 0;\n\n    for(int i=1;i&lt;N+1;i++){\n        for(int j=1;j&lt;W+1;j++){\n            if(w[i-1] &lt;= j){\n                \/* Taking max of both the cases i.e to take that \n                item or to ignore it.*\/\n                int a = v[i-1]+DP[i-1][j-w[i-1]];\n                int b = DP[i-1][j];\n                if(a>b) DP[i][j] = a;\n                else DP[i][j] = b;\n            }\n            else{\n                \/* If the weight of current element is greater \n                than the space left in the bag we'll ignore it.*\/\n                DP[i][j] = DP[i-1][j];\n            }\n        }\n    }\n    \/* returning answer for W space and N items *\/\n    return DP[N][W];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-4\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> def knapsack01(W,N,v,w) :\n    DP = [[0 for i in range(W+1)] for j in range(N+1)] # Defining DP \n\n    for i in range(1,N+1) :\n        for j in range(1,W+1) :\n            if w[i-1] &lt;= j : \n                # Taking max of both the cases i.e to take that \n                # item or to ignore it.\n                DP[i][j] = max(v[i-1]+DP[i-1][j-w[i-1]],DP[i-1][j]) \n\n            else :\n                # If the weight of current element is greater \n                # than the space left in the bag we'll ignore it.\n                DP[i][j] = DP[i-1][j]\n    # returning answer for W space and N items \n    return DP[N][W]\n<\/pre>\n\n\n\n<ul><li>Time Complexity of the above approach is O(N*W).<\/li><li>Space Complexity of the above approach is O(N*W).<\/li><\/ul>\n\n\n\n<h2 id=\"approach-3-space-optimized-solution\">Approach 3: (Space-optimized solution)<\/h2>\n\n\n\n<p>In the above approach, we used a 2D array to store the computed results in our DP but we can observe one thing that to compute the result for the n<sup>th<\/sup> element we just need the results for the (n-1)<sup>th<\/sup> element thus we do not need the rest of the result.<\/p>\n\n\n\n<p>Therefore, if we just get the results for the (n-1)<sup>th<\/sup> element we can reach the n<sup>th<\/sup> result.&nbsp;<\/p>\n\n\n\n<p>Thus we can reduce the size of our DP to 1D by just storing the results on different weights till the previous element.<\/p>\n\n\n\n<p><strong>Code For the above Implementation :<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int knapsack01(int W,int N,vector&lt;int> &amp;v,vector&lt;int> &amp;w) {\n    int DP[W+1]; \/\/ Defining DP \n    \/* For N = 0 defining DP[i] = 0.*\/\n    for(int i=0;i&lt;W+1;i++) DP[i] = 0;\n\n    for(int i=1;i&lt;N+1;i++){\n        for(int j=W;j>=w[i-1];j--){\n              \/* Taking max of both the cases i.e to take that \n              item or to ignore it.*\/\n              DP[j] = max(v[i-1]+DP[j-w[i-1]],DP[j]);\n        }\n    }\n    \/* returning answer for W space and N items *\/\n    return DP[W]; \n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int knapSack(int W,int N,int v[],int w[]) {\n    int DP[] = new int[W+1]; \/\/ Defining DP     \n    \/* For N = 0 defining DP[i] = 0.*\/\n    for(int i=0;i&lt;W+1;i++) DP[i] = 0;\n\n    for(int i=1;i&lt;N+1;i++){\n        for(int j=W;j>=w[i-1];j--){\n                \/* Taking max of both the cases i.e to take that \n                item or to ignore it.*\/\n                int a = v[i-1]+DP[j-w[i-1]];\n                int b = DP[j];\n                if(a>b) DP[j] = a;\n                else DP[j] = b;\n        }\n    }\n    \/* returning answer for W space and N items *\/\n    return DP[W];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def knapsack01(W,N,v,w) :\n    DP = [0 for i in range(W+1)] # Defining DP \n\n    for i in range(1,N+1) :\n        for j in range(W,w[i-1]-1,-1) :\n                # Taking max of both the cases i.e to take that \n                # item or to ignore it.\n                DP[j] = max(v[i-1]+DP[j-w[i-1]],DP[j]) \n    # returning answer for W space and N items \n    return DP[W]\n\n<\/pre>\n\n\n\n<ul><li><strong>Time Complexity<\/strong> of the above approach is O(N*W).<\/li><li><strong>Space Complexity<\/strong> of the above approach is O(W).<\/li><\/ul>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/0-1-knapsack\/\" target=\"_blank\">0-1 Knapsack<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-can-we-solve-the-01-knapsack-problem-using-backtracking\"><span id=\"q-1-can-we-solve-the-0-1-knapsack-problem-using-backtracking\">Q.1: Can we solve the 0\/1 Knapsack Problem using Backtracking?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Yes, the recursive DP approach itself is the backtracking approach for 0\/1 knapsack.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-time-complexity-of-01-knapsack-problem\"><span id=\"q-2-what-is-the-time-complexity-of-0-1-knapsack-problem\">Q.2: What is the Time Complexity of 0\/1 Knapsack Problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The time complexity for the 0\/1 Knapsack problem solved using DP is O(N*W) where N denotes the number of items available and W denotes the capacity of the knapsack.<\/p>\n\n\n\n<h3 id=\"q3-can-we-solve-the-01-knapsack-problem-using-greedy-algorithm\"><span id=\"q-3-can-we-solve-the-0-1-knapsack-problem-using-greedy-algorithm\">Q.3: Can we solve the 0\/1 Knapsack Problem using Greedy Algorithm?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> No, the 0\/1 Knapsack Problem cannot be solved using a greedy approach.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a Knapsack\/Bag with W weight capacity and a list of N items with given vi&hellip;\n","protected":false},"author":4,"featured_media":3417,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[536],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3398"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3398"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3398\/revisions"}],"predecessor-version":[{"id":22946,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3398\/revisions\/22946"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3417"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}