Bölmə problemi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Çiy kərpic Amazon alma Bloomberg ByteDance eBay Facebook Goldman Sachs google microsoft VMware Yahoo
Geyim Dinamik proqramlaşdırmaBaxılıb 405

Problem bəyanat

Bölmə problemində, n elementi olan bir sıra verdik. Verilən çoxluğun alt qruplardakı elementlərin cəminin bərabər olduğu iki dəstə bölünə biləcəyini tapın.

misal

Input

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

Buraxılış

bəli

Izahat

Dizini bərabər cəmi {2, 4, 5} və {11, 9, 8} olan 3 alt qrupa bölmək olar.

Input

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

Buraxılış

Yox

Izahat

The array bərabər cəmi olan 2 alt qrupa bölmək olmaz.

Yanaşma 1

Alqoritm

1. Bərabər cəmi olan 2 alt dəstin olub-olmadığını yoxlamaq üçün bölmə funksiyası yaradın.

2. Bu funksiyası,

  • Dizidəki elementlərin cəmini hesablayın.
  • Cəmi tək olduqda, yalnış qayıdın.
  • Sum = sum / 2 olan massivdə başqa subsetSum zəng edin.

3. SubsetSum, verilənlərin cəminə bərabər bir cəmi olan bir alt çoxluğun olub olmadığını tapmaqdır.

4. Bu funksiyada SubsetSum rekursiv bir yanaşma istifadə edir,

  • Son element cəmdən böyükdürsə, buna əhəmiyyət verməyin və ölçünü -1 ​​ölçüsünə endirərək davam edin.
  •  Başqa bir şey, son element daxil olmaqla və ya son element xaricində əldə edilə bilən cəmin dəyərini yoxlayın.
  • Cəmi = 0 olarsa, doğru qayıdır.
  • Ölçü = 0, lakin cəmi sıfıra bərabər deyilsə, yalan qayıdır.

Həyata keçirilməsi

Bölmə Problemi üçün C ++ Proqramı

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

Bölmə Problemi üçün Java Proqramı

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

Bölmə Problemi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (2 ^ n) burada n - verilmiş çoxluqdakı rəqəmlər.

Kosmik Mürəkkəblik

O (n)  çünki burada yığının maksimum ölçüsü n-dir.

Yanaşma 2

Alqoritm

Burada istifadə edirik dinamik proqramlaşdırma,

1. 2B array partition_array ölçüsü cəmi / 2 + 1 və n + 1 yaradın.

2. Bu massivdə,

  •  [J-1] massivinə qədər elementlərin alt dəsti cəmi bərabərdirsə, həqiqətən də saxlayın.
  • Başqa bir şey, saxta saxla.

3. Bölüm_array [sum / 2] [n] qayıt.

Həyata keçirilməsi

Bölmə Problemi üçün C ++ Proqramı

#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";
  }
}

Bölmə Problemi üçün Java Proqramı

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

Bölmə Problemi üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

O (cəmi * n) burada cəm bütün elementlərin əlavə edilməsini və n verilənlərin çoxluğunu göstərir.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir yer istifadə etmirik.

References

Translate »