Alt məbləğ problemi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon Ameyo
Geyim Dinamik proqramlaşdırmaBaxılıb 121

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Alt cəm problemində bizə a verilir siyahı bütün müsbət rəqəmlərdən və bir cəmdən. Cəmi verilən cəmə bərabər olan bir alt dəstin olub olmadığını yoxlamalıyıq.

misal

Input

Nömrələrin siyahısı: 1 2 3 10 5

cəmi: 9

Buraxılış

 doğru

Izahat

 verilmiş cəmə bərabər olan bütün dəyərlərin (1,3,5 + 1 + 3) = 5 cəmi {9} cəmi. Buna görə cavabımız bəli.

Alt cəm problemi üçün yanaşma

  • Verilən siyahıdakı hər bir element üçün iki seçimimiz var.
  1. Elementi alt qrupa daxil etmək
  2. Elemanı alt çoxluqdan xaric etmək.
  •  Elementi alt qrupa daxil etsək, cəmin dəyəri elementin dəyəri ilə azalır.
  • Elementi xaric etsək, cəmin dəyəri eyni qalır.
  • Cəmi dəyəri sıfıra enirsə, hər bir element üçün bu addımları təkrarladıqdan sonra cəmi verilən cəmə bərabər olan bir alt dəstimiz var və biz doğruduruq.
  • Əks təqdirdə, yalançı qayıdırıq.

Alt məbləğ problemiPin

Rekursiv həll

 C ++ kodu

#include <stdio.h> 
bool check(int a[], int n, int sum) 
{ 
if (sum == 0) 
  return true; 
if (n == 0 && sum != 0) 
  return false; 
if (a[n-1] > sum) 
  return check(a, n-1, sum); 
return check(a, n-1, sum) || 
            check(a, n-1, sum-a[n-1]); 
} 
int main() 
{ 
int a[] = {3, 34, 4, 12, 5, 2}; 
int sum = 9; 
int n = sizeof(a)/sizeof(a[0]); 
if (check(a, n, sum) == true) 
  printf("Found"); 
else
  printf("Not found"); 
return 0; 
}
Found

Java kodu

class subset { 
  
  static boolean check(int a[], 
              int n, int sum) 
  { 
    if (sum == 0) 
      return true; 
    if (n == 0 && sum != 0) 
      return false; 
    if (a[n-1] > sum) 
      return check(a, n-1, sum); 
    return check(a, n-1, sum) || 
      check(a, n-1, sum-a[n-1]); 
  } 
  public static void main (String args[]) 
  { 
    int a[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = a.length; 
    if (check(a, n, sum) == true) 
      System.out.println("Found"); 
    else
      System.out.println("Not found"); 
  } 
}
Found

Alt cəm problemi üçün komplekslik analizi

Zaman mürəkkəbliyi

Rekursiv yanaşma verilmiş siyahının bütün mümkün alt hissəsini yoxlayacaqdır. Beləliklə, zamanın mürəkkəbliyi eksponent olacaqdır.

Alt cəm problemi üçün dinamik proqramlaşdırma yanaşması

Rekursiv yanaşma verilmiş siyahının bütün mümkün alt hissəsini yoxlayacaqdır. Alt problem kiçik hesablanmış alt problemləri dəfələrlə çağırır. Beləliklə, eyni alt problemin yenidən hesablanmaması üçün istifadə edəcəyik dinamik proqramlaşdırma. Bir alt problemi hesablandıqdan sonra onu yadda saxlayacağıq və yenidən hesablamağımız lazım olduqda birbaşa istifadə edəcəyik. Zamanın mürəkkəbliyi dinamik proqramlaşdırma yanaşma O (n * cəm) dir.

C ++ kodu

bool check(int a[], int n, int sum) 
{ 
  bool subset[n+1][sum+1]; 
  for (int i = 0; i <= n; i++) 
  subset[i][0] = true; 
  for (int i = 1; i <= sum; i++) 
  subset[0][i] = false; 
  for (int i = 1; i <= n; i++) 
  { 
  for (int j = 1; j <= sum; j++) 
  { 
    if(j<a[i-1]) 
    subset[i][j] = subset[i-1][j]; 
    if (j >= a[i-1]) 
    subset[i][j] = subset[i-1][j] || 
                subset[i - 1][j-a[i-1]]; 
  } 
  } 
  
  return subset[n][sum]; 
} 

int main() 
{ 
int a[] = {3, 34, 4, 12, 5, 2}; 
int sum = 9; 
int n = sizeof(a)/sizeof(a[0]); 
if (check(a, n, sum) == true) 
  printf("Found"); 
else
  printf("Not found"); 
return 0; 
}
Found

Java kodu

class checksubset { 
  static boolean check(int a[], 
              int n, int sum) 
  { 
    boolean subset[][] = 
          new boolean[sum+1][n+1]; 
    for (int i = 0; i <= n; i++) 
      subset[0][i] = true; 
    for (int i = 1; i <= sum; i++) 
      subset[i][0] = false; 
    for (int i = 1; i <= sum; i++) 
    { 
      for (int j = 1; j <= n; j++) 
      { 
        subset[i][j] = subset[i][j-1]; 
        if (i >= a[j-1]) 
        subset[i][j] = subset[i][j] || 
          subset[i - a[j-1]][j-1]; 
      } 
    } 
  
  
    return subset[sum][n]; 
  } 
  public static void main (String args[]) 
  { 
    int a[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = a.length; 
    if (check(a, n, sum) == true) 
      System.out.println("Found"); 
    else
      System.out.println("Not found"); 
  } 
}
Found

Alt cəm problemi üçün komplekslik analizi

Zaman mürəkkəbliyi

O (cəmi * n) burada cəm verilir və n - dəki elementlərin sayıdır array. Problemi həll etmək üçün 2B matrisdən keçirik və cavab sağ alt küncdə alınır matris.

Kosmik mürəkkəblik

O (cəmi * n) Yaddaş üçün 2 ölçülü bir sıra istifadə edirik.

References 

 

Crack Sistemi Dizayn Müsahibələri
Translate »