시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
우리는 약간의 무게를 지탱할 수있는 배낭이 주어졌고, 우리는 주어진 품목에서 약간의 가치가있는 품목 중 일부를 선택해야합니다. 배낭의 가치 (수집 된 품목의 총 가치)가 최대화되도록 품목을 선택해야합니다. 또한 피킹 한 아이템의 무게가 배낭의 가치를 초과하지 않도록주의해야합니다. 여기에서 큰 배낭 무게를 가질 수 있습니다. 우리는 항목을 나눌 수 없습니다. 즉, 항목의 절반 또는 0/1을 취할 수 없습니다. 따라서 우리는 문제에 0-1 Knapsack Problem이라는 이름을 부여하는 항목을 사용하거나 사용하지 않습니다. 배낭은 무게가 클 수 있으므로 XNUMX-XNUMX 배낭 문제에 대한 공간 최적화 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 = 배낭에 넣을 수있는 무게, 이것은 공간 복잡성이 줄어 듭니다.
