0-1 배낭 문제는 동적 프로그래밍의 개념에 기초한 가장 중요한 문제 중 하나입니다. 동적 프로그래밍(DP)은 최적화 문제를 해결하기 위한 알고리즘 개념입니다. 간단히 말해서, 우리는 문제를 하위 문제로 나누고 최적의 전체 솔루션으로 이어지는 최적의 솔루션을 찾으려고 합니다. 먼저 문제 설명을 이해합시다.

문제 설명

특정 값을 갖는 n개의 가중치가 주어지면 이 가중치를 주어진 용량(maxWeight)의 배낭에 넣습니다. 무게 추가 후 배낭의 총 무게는 용량(maxWeight)보다 작거나 같아야 합니다. 여기서 목표는 배낭에서 가능한 최대 총 가치를 찾는 것입니다. 모든 가중치는 한 번만 선택할 수 있습니다. 예를 들어 :

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

위의 예에서 weights:{3,1}와 value:{2,3}는 각각 가중치 조합 중 최대값인 5의 합계를 가집니다.

관찰

여기서 주요 관찰은 무게 합이 배낭의 용량보다 작거나 같고 최대 값 합을 갖는 가중치의 하위 집합을 찾아야 한다는 것입니다.

재귀적 접근

재귀적으로 인덱스 0에서 n-1로 이동하고 두 가지 작업을 수행합니다.

현재 가중치를 추가합니다(하위 집합에 요소 추가). 선택 후 배낭 내부의 총 무게가 주어진 용량 미만으로 남아 있는 경우에만 현재 무게를 선택하고 그렇지 않으면 무시합니다.

현재 가중치를 추가하지 마십시오(요소를 하위 집합에 추가하지 마십시오).

수행 후 다음 요소를 재귀적으로 호출할 것입니다. 조건에 따라 위에 제공된 작업 중 하나 또는 둘 모두일 수 있습니다. 최대 총 값을 찾아야 하므로 두 작업의 최대값을 반환합니다. 배열 크기를 초과하면 중지하고 돌아와야 합니다. 따라서 결국 특정 값을 가진 가중치를 선택하거나 무시하도록 선택한 모든 하위 집합의 최대값을 갖게 됩니다.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }

            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);

            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i + 1, n, wt, val, maxWeight, dp));
            }

            return dp[i][curWeightSum];
        }

        int knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];

                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

메모화 - 여기에서는 반복되는 재귀 호출에 대해 dp에 저장된 값을 사용할 수 있도록 재귀 호출을 저장하기 위해 2차원 배열인 'dp'를 사용했습니다. 이것은 시간 복잡도를 줄이는 데 유용합니다.

시간 복잡도: O(n*maxWeight). 우리는 대부분의 반복되는 전화를 피했습니다.
공간 복잡도: O(n*maxWeight). 2차원 배열 dp를 추가 공간으로 사용했습니다.

동적 접근

이 경우 1차원 배열을 사용하여 표를 작성합니다. 치수가 maxWeight+1(배낭의 용량)과 동일한 치수입니다. 여기서 우리는 재귀 접근 방식에 명시된 동일한 두 가지 작업을 수행합니다.

용량 j의 배낭을 형성해야 하고 현재 가중치를 weight[i]로 고려하고 있으며, 이는 <=j이고 value[i]입니다. 배낭에 현재 weight[i]를 더하면 이전 반복까지의 총 무게(j-weight[i])의 배낭에 대한 최대값을 찾은 다음 weight[i] weight의 값[i]을 더해야 합니다. 그 안에. 총 중량(j-weights[i])의 배낭이 없는 경우 0이 추가되고 현재 weight[i]의 값[i]은 해당 특정 배낭에 대한 값의 합계가 됩니다. 현재 무게가 3이고 j=5가 필요하면 무게가 5-3=2인 배낭을 찾아야 합니다.

가중치를 선택하지 않으면 dp 배열의 해당 셀 값이 해당 특정 j에 대한 이전 반복에 대한 답이 됩니다.

int dp[maxWeight+1];
for(int i=0;i<maxWeight+1;i++){
   dp[i]=0;
}
for(int i=0;i<n;i++){
   for(int j=maxWeight;j>=wt[i];j--){
       dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
   }
}
return dp[maxWeight];

여기서 dp 배열의 셀 값은 operation1과 operation2의 최대값이 됩니다. 1차원 배열을 사용했습니다. 여기서 j번째 셀은 특정 i번째 가중치에 대한 작업을 수행하는 동안 가중치 j가 있는 배낭을 나타냅니다. 따라서 배열은 i번째 가중치에 대해 실행되는 동안 (i-1)번째 가중치까지 결과를 유지합니다. dp[maxWeight]를 반환하면 답이 나옵니다. 초기에 배열의 모든 값은 빈 배낭의 최대값이 0이므로 0입니다.

시간 복잡도: O(n*maxWeight).
공간 복잡도: O(maxWeight). 2차원 배열 dp를 추가 공간으로 사용했습니다.