නැප්සැක් ගැටළුව  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ MakeMyTrip Snapdeal වීසා Zoho
අරා ගතික වැඩසටහන්කරණය නැප්සැක්

“නැප්සැක් ගැටලුව” වෙත යාමට පෙර පළමුව සැබෑ ජීවිතයේ ගැටලුවක් දෙස බලන්න. සාක්කි උයනේ උපරිම එළවළු රැගෙන යාමට අවශ්යයි. කෙසේ වෙතත්, ඇගේ ගෝනියේ උපරිම බර ධාරිතාවක් ඇති අතර අමතර බර එකතු කිරීම බිඳ දැමිය හැකිය.

තත්වය සොයා බලමු-

අයිතම: {අර්තාපල්, තක්කාලි, ඉඟුරු, සුදුළූණු, බණ්ඩක්කා}
බර: {2,3,1,4,6}
ලාභ: {4,5,3,7,8}
KnapSack ධාරිතාව: 7

මේ අනුව අපට සාක්ෂා ලබා ගත හැකි මාර්ගයක් සොයා ගත යුතුය උපරිම ලාභ එළවළු වලින් ගෝනිය කඩන්නේ නැතිව.

නැප්සැක් ගැටළුව සඳහා තිරිසන් බල ප්‍රවේශය  

එසේ කිරීමේදී අපට පහත ප්‍රවේශය ඇත

  • හැකි සියලුම අයිතම කට්ටල සලකා බැලීම
  • ඒ සියල්ලේ මුළු බර හා වටිනාකම ගණනය කිරීම
  • බර සීමාව ඉක්මවා නොයන උපරිම අගය සමඟ උප කුලකය තෝරා ගැනීම.

එසේ සලකා බලන විට:

සෑම නව අයිතමයක් සඳහාම අපට තේරීම් දෙකක් තිබේ

  • We දැමිය හැකිය එය නැප්සැක් (1) තුළට:

ගෝනියේ වටිනාකම =උපරිම ලබාගත් අගය n-1 අයිතම වලින්

  • We කරන්න බැහැ එය KnapSack (0) තුළට දමන්න:

ගෝනියේ වටිනාකම =උපරිම ලබාගත් අගය n-1 අයිතම + අපගේ n වන අයිතමයේ වටිනාකම කොහෙද ධාරිතාව බෑගයේ දැන් n වන අයිතමයේ ධාරිතාව-බර දක්වා හැකිලීම.

නම් අයිතමයක බර වැඩි ය KnapSack හි ධාරිතාවට වඩා එය ඇතුළත් කළ නොහැක අපිට කරන්න වෙනවා ඉතිරි අයිතම ගැන සොයා බලන්න අපිත් එක්ක ඉන්නවා.

මෙයද බලන්න
රවුම් අරා භාවිතා කරමින් Deque ක්‍රියාත්මක කිරීම

එය ක්‍රියාත්මක කිරීම පිළිබඳව සොයා බලමු:

ජාවා වැඩසටහන

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 හි උපරිම ධාරිතාව: 15kg.

නැප්සැක් ගැටළුවපින්

(1,10) වෙත බහුවිධ ඇමතුම් ලබා ගැනීම අපට පෙනේ, එය වැඩි බර හා අගයන් සම්බන්ධ විශාල පරීක්ෂණ අවස්ථා සමඟ වැඩ කිරීම නරක අතට හැරේ. එවැනි විසඳුමකට බොහෝ කාලයක් අවශ්‍ය වන අතර a O (n ^ 2) හි කාල සංකීර්ණත්වය

අපට දියුණු විය හැක්කේ කෙසේද?  

එකම ගැටළුව නැවත නැවතත් විසඳා නොගත යුතුය. අපට එය කළ හැක්කේ කෙසේද? ප්‍රති results ල සහායකයක ගබඩා කිරීමෙන් අරාව/ වගුව ඔවුන්ට ප්‍රවේශ විය හැකි ස්ථානයෙන්.

නැප්සැක් ගැටළුව සඳහා ජාවා වැඩසටහන

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);
  }
}

සී ++ වැඩසටහන

#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

නැප්සැක් ගැටළුව සඳහා සංකීර්ණතා විශ්ලේෂණය

Voila, කාල සංකීර්ණතාව දැන් O (n * max) දක්වා අඩු වන අතර එහිදී n = නැත. අයිතම සහ උපරිම = අපගේ නැප්සැක්ට තබා ගත හැකි උපරිම බර.

මෙයද බලන්න
ගමන් වාර දෙකක් භාවිතා කරමින් ජාලක උපරිම ලකුණු එකතු කරන්න

ආශ්රිත