0-1 배낭 문제에 대한 공간 최적화 DP 솔루션

난이도 중급
자주 묻는 질문 아마존 BlackRock ByteDance 코드네이션 JP 모건 네트 스코프 올라 택시 퀄컴
동적 프로그래밍 배낭조회수 82

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

우리는 약간의 무게를 지탱할 수있는 배낭이 주어졌고, 우리는 주어진 품목에서 약간의 가치가있는 품목 중 일부를 선택해야합니다. 배낭의 가치 (수집 된 품목의 총 가치)가 최대화되도록 품목을 선택해야합니다. 또한 피킹 한 아이템의 무게가 배낭의 가치를 초과하지 않도록주의해야합니다. 여기에서 큰 배낭 무게를 가질 수 있습니다. 우리는 항목을 나눌 수 없습니다. 즉, 항목의 절반 또는 0/1을 취할 수 없습니다. 따라서 우리는 문제에 0-1 Knapsack Problem이라는 이름을 부여하는 항목을 사용하거나 사용하지 않습니다. 배낭은 무게가 클 수 있으므로 XNUMX-XNUMX 배낭 문제에 대한 공간 최적화 DP 솔루션을 찾으십시오.

0-1 배낭 문제에 대한 공간 최적화 DP 솔루션

Number of Items = 3
Weight of Knapsack = 4
Weight of given items = {4, 5, 1}
Value of given items = {10, 20, 30}
30

설명 : 최상의 결과 (또는 최대 값)를 제공하기 때문에 마지막 요소를 선택합니다.

 

Number of Items = 5
Weight of Knapsack = 50
Weight of given items = {10, 10, 10, 10, 10}
Value of given items = {1, 2, 3, 4, 5}
15

설명 : 배낭 무게가 모든 항목의 총 무게와 같으므로 모든 항목을 간단히 선택할 수 있습니다.

 

0-1 배낭 문제에 대한 공간 최적화 DP 솔루션에 대한 접근 방식

일반적으로 우리는 0-1 배낭 사용 동적 프로그래밍. 이 중 하나입니다 표준 동적 프로그래밍 문제와 다른 많은 표준 동적 프로그래밍 문제는 동일한 패턴을 따릅니다.

dp[i][j] = operation(dp[i-1][j], dp[i-1][j-wt[i] + val[i])

Here dp[i-1][j] represents we did not take the current item and

         dp[i-1][j-wt[i]] shows the reduced subproblem.

작업이란 일반적으로 수량을 최대화하거나 최소화한다는 의미입니다.

이 접근 방식에서 발생하는 유일한 문제는 XNUMX 차 공간 복잡성입니다. 우리는 일반적으로 배낭의 무게 x 항목 수의 dp 배열 또는 dp 테이블을 만듭니다. 메모리가 부족한 경우. 표준 배낭 솔루션을 더욱 최적화 할 수 있습니다. 재귀 공식을 살펴보면 dp 매트릭스의 모든 상태가 바로 위 또는 왼쪽에있는 셀에 따라 달라진다는 통찰력을 얻을 수 있습니다. 그런 다음 dp 테이블의 두 행인 첫 번째 현재 행과 두 번째 행을 현재 행 앞의 행으로 유지할 수 있습니다. 이제 문제는이 두 행을 사용하는 것으로 귀결된다고 말할 수 있습니다. 홀수 인덱스 행에 두 번째 행을 사용하고 짝수 인덱스 행에 첫 번째 행을 사용하면 문제를 해결할 수 있습니다.

여기에 설명 된 접근 방식은 Subset Sum 등과 같이 동일한 패턴을 따르는 모든 문제에 적용 할 수 있습니다.

암호

C + + 암호

#include<bits/stdc++.h>
using namespace std;
int main()
 {
  int t;cin>>t;
  while(t--){
      int numberOfItems;cin>>numberOfItems;
      int weightOfKnapsack;cin>>weightOfKnapsack;
      int wt[numberOfItems],val[numberOfItems]; // store the weight and value of each item
      
      //Taking input
      for(int i=0;i<numberOfItems;i++)
          cin>>val[i];
      for(int i=0;i<numberOfItems;i++)
          cin>>wt[i];
     
      //dp array to store the max value which can be achieved at any weight
      int dp[2][weightOfKnapsack+1];
      
      memset(dp,0,sizeof dp); //initialising the dp array to 0
      
      for(int i=0;i<numberOfItems;i++){
          for(int j=0;j<=weightOfKnapsack;j++){
              dp[i&1][j] = max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j] : 0));
              if(j>=wt[i])
                  dp[i&1][j] = max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j-wt[i]] : 0)+val[i]);
          }
      }
      
      cout<<dp[(numberOfItems-1)&1][weightOfKnapsack]<<endl;
  }
}
2

3 // number of items

4 // weight knapsack can hold

10 20 30 // value of items

4 5 1 // weight of items

3

3

10 2 3

4 50 60
30 
0

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
    	int t = sc.nextInt();
    	
    	while(t-- > 0){
    	    int numberOfItems = sc.nextInt();
    	    int weightOfKnapsack = sc.nextInt();
    	    
    	    // store the weight and value of each item
    	    int wt[] = new int[numberOfItems];
    	    int val[] = new int[numberOfItems]; 
    	    
    	    //Taking input
    	    for(int i=0;i<numberOfItems;i++)
    	        val[i] = sc.nextInt();
    	    for(int i=0;i<numberOfItems;i++)
    	        wt[i] = sc.nextInt();
    	   
    	    //dp array to store the max value which can be achieved at any weight
    	    int dp[][] = new int[2][weightOfKnapsack+1];
    	    
    	    //initialising the dp array to 0
    	    for(int i=0;i<2;i++) {
    	        for(int j=0;j<weightOfKnapsack+1;j++)
    	            dp[i][j] = 0;
    	    }
    	    
    	    for(int i=0;i<numberOfItems;i++){
    	        for(int j=0;j<=weightOfKnapsack;j++){
    	            dp[i&1][j] = Math.max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j] : 0));
    	            if(j>=wt[i])
    	                dp[i&1][j] = Math.max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j-wt[i]] : 0)+val[i]);
    	        }
    	    }
    	    
    	    System.out.println(dp[(numberOfItems-1)&1][weightOfKnapsack]);
    	}
    }
}

 

2

3 // number of items

4 // weight knapsack can hold

10 20 30 // value of items

4 5 1 // weight of items

3

3

10 2 3

4 50 60
30 
0

 

복잡성 분석

시간 복잡성: O (N * W)

여기서 N = 항목 수

W = 배낭에 넣을 수있는 무게

N = W이면 시간 복잡도 = O (N ^ 2)

공간 복잡성: O (W)

여기서 W = 배낭에 넣을 수있는 무게, 이것은 공간 복잡성이 줄어 듭니다.

균열 시스템 설계 인터뷰
Translate »