የማጥበቂያው ችግር


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ MakeMyTrip Snapdeal ቪዛ ቮሆ
ሰልፍ ተለዋዋጭ ፕሮግራም ቁራጭ

ወደ “The Knapsack ችግሩ” ከመሄድዎ በፊት በመጀመሪያ የእውነተኛ-ህይወት ችግርን ይመልከቱ ፡፡ ሳክሺ ከፍተኛውን አትክልቶች ከአትክልቱ ውስጥ ለመውሰድ ይፈልጋል ፡፡ ሆኖም ጆንያዋ ከፍተኛ የክብደት አቅም ስላላት ተጨማሪ ክብደት በመጨመር ላይ ይሰበር ይሆናል ፡፡

ሁኔታውን እንመልከት-

ዕቃዎች-{ድንች ፣ ቲማቲም ፣ ዝንጅብል ፣ ነጭ ሽንኩርት ፣ ኦክራ}
ክብደቶች ፦ {2,3,1,4,6}
ትርፍ: {4,5,3,7,8}
የ KnapSack አቅም: 7

ስለሆነም ሳክሺ የሚያገኝበትን መንገድ መፈለግ አለብን ከፍተኛ ትርፍ ከአትክልቶቹ ውስጥ ጆንያውን ሳይሰብር.

ለናፕስክ ችግር የጭካኔ ኃይል አቀራረብ

እንዲህ እያደረግን የሚከተለው አካሄድ አለን

  • ሁሉንም ሊሆኑ የሚችሉ የንጥሎች ስብስቦችን ከግምት ውስጥ በማስገባት
  • የሁላቸውን ጠቅላላ ክብደት እና ዋጋ በማስላት ላይ
  • ከክብደት ገደቡ በማይበልጥ ከፍተኛውን ንዑስ ክፍል መምረጥ።

ይህንን ከግምት ውስጥ በማስገባት-

ለእያንዳንዱ የኒት ንጥል ሁለት ምርጫዎች አሉን

  • We ማስቀመጥ ይችላል ወደ Knapsack (1):

የጆንያ ዋጋ =ከፍተኛ የተገኘ እሴት ከ n-1 ዕቃዎች

  • We አልችልም ወደ KnapSack (0) ውስጥ ያስገቡት

የጆንያ ዋጋ =ከፍተኛ የተገኘው እሴት ከ n-1 ንጥሎች + የእኛ nth ንጥል ዋጋ ችሎታ የከረጢቱ አሁን የ nth ንጥል ወደ አቅም-ክብደት መቀነስ።

የ ከሆነ የአንድ ዕቃ ክብደት ይበልጣል ከ “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);
  }
}

ሲ ++ ኮድ

#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 ከፍተኛ አቅም 15 ኪ.ግ.

የማጥበቂያው ችግር

ለ (1,10) ብዙ ጥሪዎች ሲደረጉ እናያለን ፣ ይህም ክብደቶችን እና እሴቶችን ከሚያካትቱ ትላልቅ የሙከራ ጉዳዮች ጋር አብሮ በመስራት የከፋ ይሆናል። እንዲህ ዓይነቱ መፍትሔ እንዲሁ ብዙ ጊዜ ይፈልጋል እና አለው የጊዜ ውስብስብነት (n ^ 2)

እንዴት ማሻሻል እንችላለን?

እኛ አንድ አይነት ችግር ደጋግመን አንፈታውም ተብሏል ፡፡ እኛ እንዴት ማድረግ እንችላለን? ውጤቱን በረዳት ውስጥ በማከማቸት ደርድር/ ሊደረስባቸው ከሚችሉበት ጠረጴዛ ፡፡

የጃቫ ፕሮግራም ለ ‹ናፕስክ› ችግር

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 = የለም። የንጥሎች እና ከፍተኛ = ከፍተኛ የክብደት መጠቅለያችን መያዝ ይችላል።

ማጣቀሻዎች