배낭 문제

난이도 중급
자주 묻는 질문 MakeMyTrip 스냅 딜 비자, 조호 (Zoho)
배열 동적 프로그래밍 배낭조회수 43

“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)로 줄어 듭니다. 아이템의 수와 최대 = 우리 배낭이 담을 수있는 최대 무게.

참조

Translate »