0/1 Knapsack Problem GeeksForGeeks 경계 및 무한 모두

N개 항목의 무게와 값이 주어지면 이 항목을 용량 W의 배낭에 넣어 배낭의 최대 총 값을 얻습니다. 우리는 각 항목의 수량이 하나만 있습니다.
즉, 각각 N 항목과 관련된 값과 가중치를 나타내는 두 개의 정수 배열 val[0..N-1] 및 wt[0..N-1]이 주어집니다. 또한 배낭 용량을 나타내는 정수 W가 주어지면 이 하위 집합의 가중치 합이 W보다 작거나 같도록 val[]의 최대 값 하위 집합을 찾습니다. 항목을 깰 수 없습니다. 전체 항목을 선택하거나 선택하지 마십시오. 그것을 선택하십시오 (0-1 속성).

예 1:

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

해결책:

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);
    }
}

O(n)의 스택 공간을 제거합니다. 즉, n번 스택은 최악의 경우에 생성됩니다.

표 방식 사용(하향식 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];

    } 

무한한 0/1 배낭

참고: 각 항목은 여러 번 사용할 수 있습니다.

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);
    }
}