ナップサック問題


難易度 ミディアム
よく聞かれる MakeMyTrip Snapdeal ビザ Zohoの
配列 動的計画法 ナップザック

「ナップサック問題」に進む前に、まず実際の問題を見てください。 サクシは庭から最大限の野菜を運び去りたいと思っています。 ただし、彼女の袋には最大の耐荷重があり、余分な重量を追加すると破損する可能性があります。

状況を調べてみましょう-

アイテム:{ポテト、トマト、ジンジャー、ニンニク、オクラ}
重み:{2,3,1,4,6}
利益:{4,5,3,7,8}
KnapSack容量:7

したがって、サクシが 最大利益 野菜から 袋を壊さずに.

ナップサック問題に対するブルートフォースアプローチ

そうしている間、私たちは次のアプローチを持っています

  • 考えられるすべてのアイテムのセットを検討する
  • それらすべての総重量と値を計算する
  • 重み制限を超えない最大値を持つサブセットを選択します。

そう考えながら:

n番目のアイテムごとにXNUMXつの選択肢があります

  • We 置くことができます それをナップザック(1)に入れます:

袋の価値=溶解度 得られた値 n-1アイテムから

  • We 削除されたデジタルマスターを復元することはできません それをKnapSack(0)に入れます:

袋の価値=溶解度 から得られる値 n-1アイテム+ n番目のアイテムの値 どこ 容量 バッグの n番目のアイテムの容量重量に縮小します。

もし アイテムの重量が大きい KnapSackの容量より 含めることはできません そして私達はしなければならないでしょう 残りのアイテムを調べます 私たちは私たちと一緒にいます。

同じの実装を見てみましょう:

Javaプログラム

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、XNUMX}

値:{100、70、50,40、XNUMX}

KnapSackの最大容量:15kg。

ナップサック問題

(1,10)に対して複数の呼び出しが行われていることがわかります。これは、より多くの重みと値を含むより大きなテストケースで作業するにつれて悪化します。 このようなソリューションにも多くの時間が必要であり、 O(n ^ 2)の時間計算量

どうすれば改善できますか?

同じ問題を何度も解決することはないはずです。 どうすればそれができますか? 結果を補助に保存することによって 配列/ tableにアクセスできます。

ナップサック問題のためのJavaプログラム

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

ナップサック問題の複雑さの分析

出来上がり、時間計算量はO(n * max)に減少します。ここでn = noです。 アイテムの数とmax =ナップザックが保持できる最大重量。

リファレンス