زیرمجموعه با جمع قابل تقسیم بر m


سطح دشواری سخت
اغلب در ارسیسیوم سیسکو دی شاو دیرتی Expedia میندا PayU
صف برنامه نویسی پویا

بیان مسأله

مسئله "زیرمجموعه با جمع قابل تقسیم بر m" بیان می کند که به شما آرایه ای از اعداد صحیح غیر منفی و یک عدد صحیح m به شما داده می شود. حالا شما باید پیدا کنید که آیا زیرمجموعه ای وجود دارد که حاصل جمع آن بر m باشد. این حاصل جمع زیرمجموعه است که باید 0 بدست آورد در نتیجه وقتی حالت آن را با m بگیریم.

مثال

زیرمجموعه با جمع قابل تقسیم بر m

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

توضیح

زیرمجموعه دارای مقادیر {1,2،3} مجموع برای دادن 2 در نتیجه. {4 ، 6} همچنین در نتیجه 3 را جمع می کند که در XNUMX نیز قابل تقسیم است. بنابراین پاسخ درست است.

روش

بنابراین ، ما همچنین با یک مشکل مشابه مواجه شده ایم ، بررسی اینکه آیا وجود دارد مجموع زیرمجموعه برابر با یک جمع هدف است. اما در اینجا بررسی نکنید که مجموع زیرمجموعه برابر با یک مقدار داده شده است یا خیر اما باید بررسی کنیم که آیا جمع زیرمجموعه بر m قابل تقسیم است. بنابراین ما می توانیم مسئله را از نو فریم کنیم که باید بفهمیم آیا زیرمجموعه ای با مجموع = m ، 2m ، 3m ، .. و غیره وجود دارد. ما true را نادرست برمی گردانیم

بنابراین ، به جای اینکه اینگونه فکر کنید. ما مد mod را جمع می کنیم و اگر به طریقی 0 بدست آوریم مطمئن هستیم که زیرمجموعه ای وجود دارد که حاصل جمع آن بر m است. اما قبل از آن باید به چیزی اهمیت دهیم. اگر تعداد عناصر n> = m (عددی که در برابر mod آن گرفته می شود). پس پاسخ به دلیل اصل کبوتر همیشه وجود دارد. ما فقط باید با مواردی که مجموع 0 تا m-1 دارند که n <= m باشد.

بنابراین ، کل ایده پشت این روش این است که ما زیرمجموعه هایی داریم که دارای sum = j هستند ، پس می توانیم زیر مجموعه جدیدی با مجموع = (j + element_ current)٪ 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

تحلیل پیچیدگی

پیچیدگی زمان

O (M ^ 2)، زیرا ما باید مسئله را فقط وقتی حل کنیم که n <= m باشد. بنابراین حد بالا برای n m است. بنابراین پیچیدگی زمان چند جمله ای است.

پیچیدگی فضا

O (M) ، زیرا فضای مورد نیاز برای آرایه dp خطی است. فقط فضای ذخیره سازی جدول dp مورد نیاز بود و بنابراین پیچیدگی فضا خطی است.