Problem partycji

Poziom trudności Średni
Często zadawane pytania Accolita Adobe Amazonka Apple Bloomberg ByteDance eBay Facebook Goldman Sachs Google Microsoft VMware Yahoo
Szyk Programowanie dynamiczneodwiedzajacy 447

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W zadaniu partycji podaliśmy zbiór zawierający n elementów. Sprawdź, czy dany zbiór można podzielić na dwa zbiory, których suma elementów w podzbiorach jest równa.

Przykład

Wkład

arr [] = {4, 5, 11, 9, 8, 3}

Wydajność

Tak

Wyjaśnienie

Tablicę można podzielić na 2 podzbiory o równej sumie {4, 5, 11} i {9, 8, 3}

Wkład

arr [] = {2, 4, 11, 9, 8, 3}

Wydajność

Nie

Wyjaśnienie

W ramach projektu szyk nie można podzielić na 2 podzbiory o równej sumie.

Podejście 1

Algorytm

1. Utwórz funkcję ispartition, aby sprawdzić, czy zawiera 2 podzbiory o równej sumie, czy nie.

2. W tym funkcjonować,

  • Oblicz sumę elementów w tablicy.
  • Jeśli suma jest nieparzysta, zwróć fałsz.
  • W przeciwnym razie wywołaj SubsetSum na tablicy z sum = sum / 2.

3. SubsetSum polega na sprawdzeniu, czy w tablicy znajduje się podzbiór z sumą równą danej sumie.

4. W tej funkcji SubsetSum stosuje podejście rekurencyjne,

  • Jeśli ostatni element jest większy niż suma, zignoruj ​​go i przejdź dalej, zmniejszając rozmiar do rozmiaru -1.
  •  W przeciwnym razie sprawdź wartość sumy, którą można uzyskać, uwzględniając ostatni element lub z wyłączeniem ostatniego elementu.
  • Jeśli suma = 0, zwraca prawdę.
  • Jeśli rozmiar = 0, ale suma nie jest równa zeru, zwraca fałsz.

Realizacja

Program C ++ dotyczący problemu z partycjami

#include <bits/stdc++.h>
using namespace std;
 
 
//recursive method
bool SubsetSum(int array[], int n, int sum)
{
   if(sum==0)
   {
     return true;
   }
   if(n==0&&sum!=0)
   {
     return false;
   }
   //last element greater than the sum remove it and continue
   if (array[n-1]>sum)
   {
     return SubsetSum(array, n-1, sum);
   }
   //include last or exclude last
   return SubsetSum(array, n-1, sum) || SubsetSum (array, n-1, sum-array[n-1]);
}
//if sum of elements is odd return false
//else find if there is a subset with sum = sum/2
bool isPartiion(int array[], int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
       sum += array[i];
    }
    if(sum%2 != 0)
    {
       return false;
    }
    return SubsetSum(array, n, sum/2);
}
 
//Main function
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
     cin>>a[i];
  }
  bool x = isPartiion(a,n);
  if(x)
  {
    cout<<"given input array can be divided into two subsets with equal sum";
  }    
  else
  {
    cout<<"given input array cannot be divided into two subsets with equal sum";
  }
  return 0;
}

Program Java dotyczący problemu z partycjami

import java.util.Scanner;
class sum
{
    //recursive method
    public static int SubsetSum(int array[], int n, int sum)
    {
       if(sum==0)
       {
         return 1;
       }
       if(n==0&&sum!=0)
       {
         return 0;
       }
       //last element greater than the sum remove it and continue
       if (array[n-1]>sum)
       {
         return SubsetSum(array, n-1, sum);
       }
       //include last or exclude last
       int x1 = SubsetSum(array, n-1, sum);
       int x2 = SubsetSum (array, n-1, sum-array[n-1]);
       if(x1==1 || x2==1)
           return 1;
       else
           return 0;
    }
    //if sum of elements is odd return false
    //else find if there is a subset with sum = sum/2
    public static int isPartiion(int array[], int n)
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
           sum += array[i];
        }
        if(sum%2 != 0)
        {
           return 0;
        }
        return SubsetSum(array, n, sum/2);
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int ans = isPartiion(arr,n);
        if(ans==1)
        {
            System.out.println("given input array can be divided into two subsets with equal sum");
        }
        else
        {
            System.out.println("given input array cannot be divided into two subsets with equal sum");
        }
    } 
}
6
1 3 2 1 1 4
given input array can be divided into two subsets with equal sum

Analiza złożoności problemu partycji

Złożoność czasowa

O (2 ^ n) gdzie n to liczby obecne w danym zbiorze.

Złożoność przestrzeni

Na)  ponieważ maksymalny możliwy rozmiar stosu to n.

Podejście 2

Algorytm

Tutaj używamy Programowanie dynamiczne,

1. Utwórz macierz 2D tablica rozmiar_tablicy_partycji suma / 2 + 1 i n + 1.

2. W tej tablicy

  •  Przechowuj naprawdę, jeśli podzbiór elementów, aż tablica [j-1] ma sumę równą i.
  • W przeciwnym razie przechowuj fałszywe.

3. Zwróć tablicę_partycji [suma / 2] [n].

Realizacja

Program C ++ dotyczący problemu z partycjami

#include <bits/stdc++.h>
using namespace std;
bool isPartiion(int array[], int n)
{
    int sum = 0,i, j;
    //sum = sum of elements in the array
    for (i = 0; i < n; i++)
    {
      sum += array[i];
    }
    //if sum is odd return false
    if (sum%2 != 0)
    {
       return false;
    }
     //partition table 2d array
    bool partition_array[sum/2+1][n+1];
    for (i = 0; i <= n; i++)
    {
      partition_array[0][i] = true;
    }
    for (i = 1; i <= sum/2; i++)
    {
      partition_array[i][0] = false;     
    }  
     for (i = 1; i <= sum/2; i++)  
     {
       for (j = 1; j <= n; j++)  
       {
         partition_array[i][j] = partition_array[i][j-1];
         if(i >= array[j-1])
         {
           partition_array[i][j] = partition_array[i][j] || partition_array[i - array[j-1]][j-1];
         }
       }        
     }   
     // uncomment this part to print table 
     for (i = 0; i <= sum/2; i++)  
     {
       for (j = 0; j <= n; j++)  
          printf ("%d ",partition_array[i][j]);
       printf("\n");
     }   
     return partition_array[sum/2][n];
}     
 
//Main
int main()
{
  int input_array[] = {1, 2, 3, 6};
  int size = sizeof(input_array)/sizeof(input_array[0]);
  bool x = isPartiion(input_array,size);
  if(x)
  {
    cout<<"given input array can be divided into two subsets with equal sum";
  }    
  else
  {
    cout<<"given input array cannot be divided into two subsets with equal sum";
  }
}

Program Java dotyczący problemu z partycjami

import java.util.Scanner;
class sum
{
    public static int isPartiion(int array[], int n)
    {
        int sum = 0,i, j;
        //sum = sum of elements in the array
        for (i = 0; i < n; i++)
        {
          sum += array[i];
        }
        //if sum is odd return false
        if (sum%2 != 0)
        {
           return 0;
        }
         //partition table 2d array
        int partition_array[][] = new int [sum/2+1][n+1];
        for (i = 0; i <= n; i++)
        {
          partition_array[0][i] = 1;
        }
        for (i = 1; i <= sum/2; i++)
        {
          partition_array[i][0] = 0;     
        }  
         for (i = 1; i <= sum/2; i++)  
         {
           for (j = 1; j <= n; j++)  
           {
             partition_array[i][j] = partition_array[i][j-1];
             if(i >= array[j-1])
             {
               if(partition_array[i][j]==1 || partition_array[i - array[j-1]][j-1]==1)
               {
                   partition_array[i][j]=1;
               }
               else
               {
                   partition_array[i][j]=0;
               }
             }
           }        
         }  
         return partition_array[sum/2][n];
    }     
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int ans = isPartiion(arr,n);
        if(ans==1)
        {
            System.out.println("given input array can be divided into two subsets with equal sum");
        }
        else
        {
            System.out.println("given input array cannot be divided into two subsets with equal sum");
        }
    } 
}
5
1 2 3 4 5
given input array cannot be divided into two subsets with equal sum

Analiza złożoności problemu partycji

Złożoność czasowa

O (suma * n) gdzie suma oznacza dodanie wszystkich elementów, a n jest rozmiarem danego zbioru.

Złożoność przestrzeni

O (1) ponieważ nie używamy tutaj żadnej spacji.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »