시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
“The Knapsack Problem”로 가기 전에 먼저 실제 문제를 살펴보십시오. Sakshi는 정원에서 최대한의 야채를 가져 가려고합니다. 그러나 그녀의 자루는 최대 무게 용량을 가지고 있으며 추가 무게로 인해 파손될 수 있습니다.
상황을 살펴 보겠습니다.
항목 : {감자, 토마토, 생강, 마늘, 오크라}
가중치 : {2,3,1,4,6}
이익 : {4,5,3,7,8}
KnapSack 용량 : 7
따라서 Sakshi가 얻을 수있는 방법을 찾아야합니다. 최대 이익 채소에서 자루를 깨지 않고.
차례
배낭 문제에 대한 무차별 대입 접근 방식
그렇게하는 동안 우리는 다음과 같은 접근 방식을 가지고 있습니다.
- 가능한 모든 항목 세트 고려
- 그들 모두의 총 무게와 가치를 계산
- 무게 제한을 초과하지 않는 최대 값으로 하위 집합을 선택합니다.
그렇게 고려하는 동안 :
n 번째 항목마다 두 가지 선택이 있습니다.
- We 넣을 수있다 Knapsack (1)에 넣습니다.
자루의 가치 =최고 얻은 가치 n-1 항목에서
- We ~ 할 수 없다. KnapSack (0)에 넣습니다.
자루의 가치 =최고 에서 얻은 값 n-1 항목 + n 번째 항목의 값 어디 생산 능력 이제 가방의 n 번째 항목의 용량 가중치로 축소됩니다.
경우 아이템의 무게가 더 크다 KnapSack의 용량보다 그것은 포함될 수 없습니다 그리고 우리는 나머지 항목 살펴보기 우리는 우리와 함께 있습니다.
동일한 구현을 살펴 보겠습니다.
자바 프로그램
import java.util.*;
public class knaprec
{
public static int knaprec(int max,int w[],int val[],int n)
{
if(n==0 || max==0)
return 0;
else if(w[n-1]>=max)
return knaprec(max,w,val,n-1);
else
return(Math.max(w[n-1]+knaprec(max-w[n-1],w,val,n-1),knaprec(max,w,val,n-1)));
}
public static void main(String args[])
{
int n=5;
int max=10;
int w[]=new int[]{12,1,2,1,4};
int val[]=new int[]{4,1,2,2,10};
int ans=knaprec(max,w,val,n);
System.out.println(ans);
}
}
C ++ 코드
#include<iostream>
int maxs(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int knaprec(int max,int w[],int val[],int n)
{
if(n==0 || max==0)
return 0;
else if(w[n-1]>=max)
return knaprec(max,w,val,n-1);
else
return(maxs(w[n-1]+knaprec(max-w[n-1],w,val,n-1),knaprec(max,w,val,n-1)));
}
int main()
{
int n=5;
int max=10;
int w[]={12,1,2,1,4};
int val[]={4,1,2,2,10};
int ans=knaprec(max,w,val,n);
cout<<ans;
}
배낭 문제에 대한 설명
우리 프로그램에서 만든 호출을 살펴 보겠습니다.
가중치 : {10, 2, 3,5}
값 : {100, 70, 50,40}
KnapSack의 최대 용량 : 15kg.
더 많은 가중치와 값을 포함하는 더 큰 테스트 케이스로 작업함에 따라 (1,10)에 대한 여러 호출이 수행되는 것을 볼 수 있습니다. 이러한 솔루션에는 많은 시간이 필요하며 O (n ^ 2)의 시간 복잡도
어떻게 개선 할 수 있습니까?
우리는 같은 문제를 몇 번이고 해결해서는 안됩니다. 어떻게 할 수 있습니까? 결과를 보조에 저장하여 정렬/ table에 액세스 할 수 있습니다.
배낭 문제를위한 자바 프로그램
import java.util.*;
class knap
{
public static int KnapSack(int max,int w[],int val[],int n)
{
int dp[][]=new int[n+1][max+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=max;j++)
{
if(i==0 || j==0)
dp[i][j]=0;
//The KnapSack cannot have any value if there are no objects added.
else if(w[i-1]<=j)
{
//val[j]=Value of the current weight
//dp[i-1][j-w[i-1]]=The value of the KnapSack when previous weight was added
//val[j]+dp[i-1][j-w[i-1]]=The value of the KnapSack in case we add the current weight
//dp[i-1][j]=The value of the KnapSack without the current weight
dp[i][j]=Math.max(val[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
}
else
dp[i][j]=dp[i-1][j];
}
}
return dp[n][max];
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=5;
int max=4;
int w[]=new int[]{12,1,2,1,4};
int val[]=new int[]{4,1,2,2,10};
int ans=KnapSack(max,w,val,n);
System.out.println(ans);
}
}
C ++ 프로그램
#include<iostream>
using namespace std;
int maxs(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int KnapSack(int max,int w[],int val[],int n)
{
int dp[n+1][max+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=max;j++)
{
if(i==0 || j==0)
dp[i][j]=0;
//The KnapSack cannot have any value if there are no objects added.
else if(w[i-1]<=j)
{
//val[j]=Value of the current weight
//dp[i-1][j-w[i-1]]=The value of the KnapSack when previous weight was added
//val[j]+dp[i-1][j-w[i-1]]=The value of the KnapSack in case we add the current weight //dp[i-1][j]=The value of the KnapSack without the current weight
dp[i][j]=maxs(val[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
}
else
dp[i][j]=dp[i-1][j];
}
}
return dp[n][max];
}
int main()
{
int n=5;
int max=4;
int w[]={12,1,2,1,4};
int val[]={4,1,2,2,10};
int ans=KnapSack(max,w,val,n);
cout<<ans;
}
8
배낭 문제에 대한 복잡성 분석
짜잔, 시간 복잡도는 이제 n = no 인 O (n * max)로 줄어 듭니다. 아이템의 수와 최대 = 우리 배낭이 담을 수있는 최대 무게.
