Подмножество със сума, делима на m  


Ниво на трудност Трудно
Често задавани в Арцезиум Cisco DE Шоу Директи Expedia Myntra PayU
Array Динамично програмиране

Декларация за проблема  

Проблемът „Подмножество със сума, делима на m“ гласи, че сте получили масив от неотрицателни цели числа и цяло число m. Сега трябва да намерите дали има подмножество със сума, делима на m. Това е сумата от подмножеството трябва да даде 0 като резултат, когато вземем неговия режим с m.

Пример  

Подмножество със сума, делима на mщифт

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

Обяснение

Подмножество със стойности {1,2} се сумира, за да даде 3 като резултат. {2, 4} също сумират, за да дадат 6 като резултат, който също се дели на 3. По този начин отговорът е верен.

Подход  

Така че, ние също се натъкнахме на подобен проблем, който е да проверим дали сума от подмножеството е равна на целева сума. Но тук не проверявайте дали сумата на подмножеството е равна на дадена сума, но трябва да проверим дали сумата на подмножеството се дели на m. Така че можем да преформулираме проблема, тъй като трябва да намерим дали има подмножество със сума = m, 2m, 3m, .. и т.н. Ако подмножеството има сума, равна на някоя от дадените стойности. връщаме true true false.

Така че, вместо да мислим по този начин. Продължаваме да приемаме мода на сумата и ако по някакъв начин получим 0. Сигурни сме, че съществува подмножество, имащо сума, делима на m. Но преди това трябва да се грижим за нещо. Ако броят на елементите n> = m (брой спрямо чий мод трябва да бъде взет). Тогава отговорът винаги съществува поради принципа на Pigeonhole. Трябва да се справим само със случаи, които имат сума от 0 до m-1, което е n <= m.

Вижте също
Намерете всички двойки (a, b) в масив, така че a% b = k

И така, цялата идея зад този подход е, че имаме някои подмножества, които имат сума = j, тогава можем да създадем ново подмножество със сума = (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

Java код за подмножество със сума, делима на 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 таблицата и по този начин сложността на пространството е линейна.