0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded

Dp Learnings (27 Part Series)

1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score

You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item.
In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or dont pick it (0-1 property).

Example 1:

Input:
N = 3
W = 4
values[] = {1,2,3}
weight[] = {4,5,1}
Output: 3

Enter fullscreen mode Exit fullscreen mode

Solution:

class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
         // your code here 
         //This is similar to subset sum equals to target
         // this can be solved using backtracking 
         //i.e taking value at an index, or not taking it
         //lets optimize it with dp
         int dp[][] = new int[n][W+1];
         for(int row[]: dp){
             Arrays.fill(row,-1);
         }
         return solve(n-1,wt,val,W,dp); // starting from the last index hence n-1;
    } 
     public static int solve(int index, int[] w, int [] val, int target,int dp[][]){
        // base case
        if(index==0){
            //we have reached the first index, and in order for the value to be accepted
            //at this index, the weight of the value at i should be equal to target
            if(w[index]<=target) return val[index];
            return 0;
        }
        if(dp[index][target]!=-1) return dp[index][target];
        int take = 0;
        if(target>=w[index]){
            take = val[index]+ solve(index-1,w,val,target-w[index],dp);
        }
        int dontTake = 0+ solve(index-1,w,val,target,dp);
        return dp[index][target] =  Integer.max(take,dontTake);
    }
}

Enter fullscreen mode Exit fullscreen mode

Removing stack space of O(n) ie for n times stack will be created in worst case

Using tabulation approach (top down dp)

//tabulation appraoch : dp top down : tc O(n*W) space complexity : O(n*W) on stack space :)
class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
         // your code here 
         //This is similar to subset sum equals to target
         // this can be solved using backtracking 
         //i.e taking value at an index, or not taking it
         //lets optimize it with dp
         int dp[][] = new int[n][W+1];
        for(int i = wt[0];i<=W;i++){
            //it means that weight at index 0 should be less than or equals to 
            // target ie weigth W
            //so every time when the weigth is less than or equals to target(W) strore val[0] in dp[0][i] ;
            dp[0][i] = val[0];
        }
         for(int i =1;i<n;i++){
             for(int tar = 0;tar<=W;tar++){
                 int take =0;
                 if(tar>=wt[i]){
                    take = val[i]+dp[i-1][tar-wt[i]];
                 }
                 int dontTake = 0+ dp[i-1][tar];
                 dp[i][tar] = Integer.max(take,dontTake);
             }
         }
          return dp[n-1][W];

    }

Enter fullscreen mode Exit fullscreen mode

Unbounded 0/1 Knapsack

Note: Each item can be taken any number of times.

class Solution{
    static int knapSack(int N, int W, int val[], int wt[])
    {
        int dp[][] = new int[N][W+1];
        for(int row[]:dp){
            Arrays.fill(row,-1);
        }
        return maxProfit(N-1,W,val,wt,dp);
    }
    public static int maxProfit(int index, int W,int [] val, int w[],int dp[][]){
        if(index==0){
             //let say at index 0 val = 10 , w[index] = 3 and W =8 ,
            // now we can consider index 0 twice ,as 3*2 =6<=8
            ///hence for twice 2*val = 2*10 = 20 , hence return 20;
            //just convert the above logic in code;
            return (W/w[index])*val[index];

        }
        if(dp[index][W]!=-1) return dp[index][W];
        int take =0;// taki
ng the same index
        if(W>=w[index]){
            take = val[index] + maxProfit(index,W-w[index],val,w,dp);
        }
        int dontTake = 0 + maxProfit(index-1,W,val,w,dp);
        return dp[index][W] =  Integer.max(take,dontTake);
    }
}

Enter fullscreen mode Exit fullscreen mode

Dp Learnings (27 Part Series)

原文链接：0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END