Мушкилоти рустакӣ


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад MakeMyTrip Snapdeal Visa Зохо
тартиботи ҳарбӣ Барномарезии динамикӣ Напасак

Пеш аз рафтан ба "Масъалаи рюкзак" аввал мушкили ҳаёти воқеиро бинед. Сакши мехоҳад максималии сабзавотро аз боғ кашонад. Аммо, халтаи вай зарфияти ҳадди вазн дорад ва метавонад ҳангоми илова кардани вазни зиёдатӣ шикаста шавад.

Биёед ба вазъ нигарем-

Ашё: {Картошка, Помидор, Занҷабил, Сирпиёз, Окра}
Вазнҳо: {2,3,1,4,6}
Фоида: {4,5,3,7,8}
Иқтидори KnapSack: 7

Мо бояд чунин роҳеро ёбем, ки Сакши онро ба даст орад фоидаи максималӣ аз сабзавот халтаро нашикаста.

Равиши бераҳмонаи маҷбурӣ барои мушкилоти рюкзак

Ҳангоми иҷрои ин амал мо чунин равиш дорем

  • Бо назардошти ҳама маҷмӯи имконпазири ашё
  • Ҳисоб кардани вазн ва арзиши ҳамаи онҳо
  • Интихоби зергурӯҳ бо арзиши ҳадди аксар, ки аз ҳадди вазн зиёд нест.

Ҳангоми баррасии чунин:

Мо барои ҳар як ҷузъи nth ду интихоб дорем

  • We гузошта метавонад онро ба ҷузвдони (1):

Арзиши халта =максимум арзиши бадастомада аз ашёи n-1

  • We не онро ба KnapSack гузошт (0):

Арзиши халта =максимум арзиши аз n-1 адад + Арзиши адад nth мо ки дар он ҷо имконият аз халта мебуд акнун ба андозаи иқтидори ашёи nth кам карда шавад.

Агар вазни ашё бузургтар аст назар ба иқтидори 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}

Арзишҳо: {100, 70, 50,40}

Иқтидори максималии KnapSack: 15кг.

Мушкилоти рустакӣ

Мо мебинем, ки зангҳои сершумор ба (1,10) зада мешаванд, ки ҳангоми кор бо парвандаҳои санҷишии калонтар бо вазну арзишҳои бештар бадтар мешаванд. Чунин ҳалли он низ вақти зиёдро талаб мекунад ва дорад мураккабии вақти O (n ^ 2)

Чӣ тавр мо метавонем беҳтар шавем?

Мо гумон мекунем, ки ҳамон масъаларо такрор ба такрор ҳал накунем. Чӣ тавр мо инро карда метавонем? Бо нигоҳ доштани натиҷаҳо дар ёрирасон асал/ ҷадвале, ки аз он ҷо дастрас шудан мумкин аст.

Барномаи 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. ашё ва макс = вазни максималии ҷузвдони мо.

Адабиёт