Bölmə bərabər alt cəm

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook google
Geyim Dinamik proqramlaşdırmaBaxılıb 31

Bölmə bərabər alt cəm verdiyimiz bir problemdir array müsbət rəqəmlər. Hər iki dəstdəki elementlərin cəmi eyni olması üçün onu iki alt qrupa bölə biləcəyimizi öyrənməliyik. Burada çoxluqda olan elementlərin sayının bərabər olması vacib deyil. Elementləri hər yerdən təsadüfi seçə bilərik, ancaq hər element yalnız bir dəfə seçir. Burada elementlərin cəmi tək bir sıra içərisindədirsə, onu iki alt hissəyə bölə bilmərik. Dizidən elementləri necə seçəcəyimizi görək hər iki dəstdəki elementlərin cəmi eyni qalacaq.

Bölmə bərabər alt cəmPin

Burada hər iki alt qrupdakı elementlərin cəmi 17-yə bərabərdir. Buna görə “YES” yazdırırıq.

Giriş Formatı

Dizidəki elementləri izah edən tam bir N dəyəri olan birinci sətir.

N tam ədədi olan ikinci sətir.

Çıxış formatı

Elementləri iki alt qrupa bölsək, yalnız "YES" olan bir sətir, əks halda "YOX" yazdırın.

Məhdudiyyətlər

  • 1 <= N <= 500
  • 1 <= A [i] <= 100
Sample Input:
8
1 5 9 6 5 4 2 2
Sample Output:
YES

İş qaydası

Sadəcə cəmin hər hansı bir alt hissəsini giriş massivinin ümumi cəminin yarısına bərabər tapıb-tapmadığımızı yoxlayırıq. Beləliklə, bunu istifadə edərək tapırıq Dinamik proqramlaşdırma yanaşma. 0 və 1-i ehtiva edən bir DP matrisi yaradırıq. Əgər hər hansı bir hüceyrədə varsa, cəmi dəyərinin doğru olduğu sütun dəyərinə bərabər bir çoxluq yarada bilərik. Yuxarıdakı nümunə ilə bu DP-ni necə yaratdığımızı görək.

Step-1

Verdiyimiz bir misal götürək = {1, 2, 5, 2}, sonra TOTAL SUM = 10 və alt cəmi = SUM = 10/2 = 5.

Başlanğıcda bütün hüceyrələrdə 0 olan N * SUM ölçülü bir dp matris yaradın.

Bölmə bərabər alt cəmPin

 

Step-2

Birinci sətirdə 1 və giriş massivinin 1-ci elementindən istifadə edərək cəmi tapdığımız sütunları təyin edin. Burada cəmi 1-ci elementdən istifadə edərək cəmi = 1 tapırıq. Beləliklə, DP matrisimiz belə görünür:

Pin

Step-3

İkinci sətirdə 1 və giriş massivinin 2 elementindən başlayaraq cəmi tapdığımız sütunları təyin edin. Burada yalnız ilk 1 elementdən istifadə edərək cəmi = {2, 3, 2} tapırıq. Beləliklə, DP matrisimiz belə görünür:

Pin

Step-4

Üçüncü sətirdə 1 və giriş massivinin 3 elementindən başlayaraq cəmi tapdığımız sütunları təyin edin. Burada yalnız ilk 1 elementdən istifadə edərək cəmi = {2, 3, 5, 3} tapırıq. Beləliklə, DP matrisimiz belə görünür:

Pin

Step-5

Dördüncü sətirdə 1 və giriş massivinin 3 elementindən başlayaraq cəmi tapdığımız sütunları təyin edin. Burada cəmi yalnız ilk dörd elementdən istifadə edərək cəmi = {1, 2, 3, 4, 5} tapırıq. Bütün satırları ziyarət etdiyimiz üçün bu, son addımımızdır. Beləliklə, DP matrisimiz belə görünür:

Pin

Burada DP seriyamızın 5-cü sətirdə və 4-ci sütunda 5 olduğu üçün elementlərin cəmi 1 olan bir alt qrup yarada bilərik.

Bu vəziyyətdə kod çıxışımız “YES” olur.

Alqoritm

Step:1 Find the sum of all the elements of the given array.
Step:2 Set SUM = total sum of elements)/2.
Step:3 Create a DP matrix of size N*(SUM+1) where N is the number of elements in the input array.
Step:4 Set all the cells of DP matrix as 0.
Step:5 For i in range 0 to N:
       Set DP[i][0] = 1
Step:6 For i in range 1 to N:
           For j in range 1 to SUM:
                If arr[i-1] <= j then:
                   DP[i][j] = (DP[i-1][j]||DP[i-1][j-arr[i-1]])
                Else:
                   DP[i][j] = DP[i-1][j].
Step:7 If DP[N][SUM] is 1 then print "YES" else print "NO".

Həyata keçirilməsi

/*C++ Implementation of Partition equal subset sum.*/ 
#include<bits/stdc++.h> 
using namespace std; 
bool partition(vector<int>nums,int sum)
{
    int n=nums.size();
    /**/
    int dp[n+1][sum+1];
    memset(dp,0,sizeof(dp));
    /*Set all cells of first column as 1.*/
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            /*update answer for each row.*/
            if(nums[i-1]<=j)
            {
                dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
            }
            else dp[i][j]=dp[i-1][j];
        }
    }
    /*return the result.*/
    return dp[n][sum];
}
bool canPartition(vector<int>& nums) 
{
    int sum=0;
    for(int i=0;i<nums.size();i++)
    {
        sum+=nums[i];
    }
    if(sum%2!=0)
    {
        return 0;
    }
    return partition(nums,sum/2);   
}
int main() 
{ 
    /*input values.*/ 
    int n;  
    cin>>n;  
    vector<int> inp; 
    for(int i=0;i<n;i++) 
    { 
       int x; 
       cin>>x; 
       inp.push_back(x); 
    }  
    /*call the function.*/
    bool flag=canPartition(inp);
    /*print the answer.*/
    if(flag)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0; 
}
4
1 2 5 2
YES

Zamanın mürəkkəbliyi

O (N * cəmi) burada N - massivdəki elementlərin sayı və SUM - massivdəki elementlərin ümumi cəminin yarısıdır. N * SUM ölçüsündə bütün DP matrislərini keçirik, buna görə də zaman mürəkkəbliyimiz O (N * SUM) olur.

Kosmik Mürəkkəblik

O (N * cəmi) burada N - massivdəki elementlərin sayı və SUM - massivdəki elementlərin ümumi cəminin yarısıdır. Elementlərdən istifadə edərək SUM əmələ gətirməyin mümkün olub-olmadığını izah edən bir DP matrisi yaradırıq. DP matrisində DP [N] [SUM] son ​​cavab haqqında ətraflı məlumat verin, buna görə bütün dəyərləri DP matrisində saxlamalıyıq.

References

Translate »