مجموعة فرعية بمجموع يقبل القسمة على م  


مستوى الصعوبة الثابت
كثيرا ما يطلب في Arcesium سيسكو دي شو Directi اكسبيديا Myntra PayU
مجموعة البرمجة الديناميكية

المشكلة بيان  

توضح مشكلة "مجموعة فرعية بمجموع قابل للقسمة على m" أنه يتم منحك مصفوفة من الأعداد الصحيحة غير السالبة وعدد صحيح م. الآن عليك معرفة ما إذا كانت هناك مجموعة فرعية يقبل مجموعها القسمة على m. هذا هو مجموع المجموعة الفرعية التي يجب أن تعطي 0 نتيجة لذلك عندما نأخذ وضعها مع m.

مثال  

مجموعة فرعية بمجموع يقبل القسمة على مدبوس

array = {1, 2, 4}
m = 3
True

تفسير

مجموعة فرعية لها قيم {1,2،3} مجموع لإعطاء 2 كنتيجة. {4، 6} يصل أيضًا إلى الناتج 3 كنتيجة قابلة للقسمة أيضًا على XNUMX. وبالتالي فإن الإجابة صحيحة.

الرسالة  

لذلك ، واجهنا أيضًا مشكلة مماثلة وهي التحقق مما إذا كان مجموع المجموعة الفرعية يساوي المجموع المستهدف. لكن هنا لا تتحقق مما إذا كان مجموع المجموعة الفرعية يساوي مبلغًا معينًا ولكننا بحاجة إلى التحقق مما إذا كان مجموع المجموعة الفرعية يقبل القسمة على m. لذا يمكننا إعادة صياغة المشكلة كما نحتاج إلى إيجاد مجموعة فرعية بها مجموع = م ، 2 م ، 3 م ، .. ، إلخ. إذا كانت المجموعة الفرعية تحتوي على مجموع يساوي أيًا من القيم المعطاة. نعود صحيح آخر خطأ.

لذا ، بدلاً من التفكير بهذه الطريقة. نستمر في أخذ نموذج الجمع وإذا حصلنا بطريقة ما على 0. نحن على يقين من وجود مجموعة فرعية بها مجموع يقبل القسمة على m. لكن علينا أن نهتم بشيء ما قبل ذلك. إذا كان عدد العناصر n> = m (الرقم الذي سيتم أخذ تعديله مقابله). إذن الإجابة موجودة دائمًا بسبب مبدأ Pigeonhole. نحتاج فقط للتعامل مع الحالات التي يكون مجموعها من 0 إلى m-1 وهو n <= m.

انظر أيضا
أوجد كل الأزواج (أ ، ب) في مصفوفة بحيث يكون a٪ b = k

لذا ، فإن الفكرة الكاملة وراء هذا النهج هي أن لدينا بعض المجموعات الفرعية التي تحتوي على sum = j ، ثم يمكننا إنشاء مجموعة فرعية جديدة بها sum = (j + current_element)٪ m. وهذه هي الطريقة التي سنملأ بها البرمجة الديناميكية الطاولة.

رمز  

كود C ++ للمجموعة الفرعية مع مجموع قابل للقسمة على m

#include<bits/stdc++.h>
using namespace std;

bool findSubsetDivisibleByM(int arr[], int n, int m)
{
  // because of piegonhole principle
  if (n > m)
    return true;

  // this will work as dp array for all elements until the last element
  bool dp[m]; memset(dp, false, m);

  for (int i=0; i<n; i++)
  {
    // this will work as our current dp array
    bool tmp[m]; memset(tmp,false,m);

    // we will add the current element to all possible subset sum
    // until now and then take the mod of the sum and will keep
    // on filling the current dp array(tmp)
    for (int j=0; j<m; j++)
    {
      // if the dp table until the last element has subset sum = j
      if (dp[j] == true)
      {
        if (dp[(j+arr[i]) % m] == false)
          // fill the current dp table(tmp array)
          tmp[(j+arr[i]) % m] = true;
      }
    }

    // now just fill the original dp array
    for (int j=0; j<m; j++)
      if (tmp[j] == true)
        dp[j] = true;
    // fill the dp array considering you have subset made of only current element
    dp[arr[i]%m] = true;
  }

  return dp[0];
}

int main(){
  // Number of elements
  int n;cin>>n;
  // Number which should divide the subset
  int m;cin>>m;
  // array to store non-negative numbers
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  bool can = findSubsetDivisibleByM(a, n, m);
  if(can == true)
    cout<<"There exists a subset having sum divisible by m";
  else
    cout<<"There does not exist any subset having sum divisible by m";
}
3 3 
1 2 4
There exists a subset having sum divisible by m

كود جافا للمجموعة الفرعية مع مجموع قابل للقسمة على m

import java.util.*;
class Main{
  
  	static boolean findSubsetDivisibleByM(int arr[], int n, int m)
  {
    // because of piegonhole principle
    if (n > m)
      return true;

    // this will work as dp array for all elements until the last element
    boolean dp[] = new boolean [m];
    for(int i=0;i<m;i++)
      dp[i] = false;

    for (int i=0;i<n; i++)
    {
      // this will work as our current dp array
      boolean tmp[] = new boolean[m];
      for(int j=0;j<m;j++)
        tmp[j] = false;
      // we will add the current element to all possible subset sum
      // until now and then take the mod of the sum and will keep
      // on filling the current dp array(tmp)
      for (int j=0; j<m; j++)
      {
        // if the dp table until the last element has subset sum = j
        if (dp[j] == true)
        {
          if (dp[(j+arr[i]) % m] == false)
            // fill the current dp table(tmp array)
            tmp[(j+arr[i]) % m] = true;
        }
      }

      // now just fill the original dp array
      for (int j=0; j<m; j++)
        if (tmp[j] == true)
          dp[j] = true;
      // fill the dp array considering you have subset made of only current element
      dp[arr[i]%m] = true;
    }

    return dp[0];
  }
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // Number of elements
    int n = sc.nextInt();
    int m = sc.nextInt();
    // array to store non-negative numbers
    int a[] = new int[n];
    for(int i=0;i<n;i++)
      a[i] = sc.nextInt();
    boolean can = findSubsetDivisibleByM(a, n, m);
    if(can == true)
      System.out.println("There exists a subset having sum divisible by m");
    else
      System.out.println("There does not exist any subset having sum divisible by m");
  	}
}
3 3
1 2 4
There exists a subset having sum divisible by m

تحليل التعقيد  

تعقيد الوقت

يا (م ^ 2)، لأنه يتعين علينا حل المشكلة فقط عندما تكون n <= m. وبالتالي فإن الحد الأعلى لـ n هو m. وبالتالي فإن تعقيد الوقت هو متعدد الحدود.

انظر أيضا
متوسط ​​النطاق في المصفوفة

تعقيد الفضاء

يا (م) ، لأن المساحة المطلوبة لصفيف dp خطية. كانت المساحة مطلوبة فقط لتخزين جدول dp ، وبالتالي يكون تعقيد المساحة خطيًا.