合計がmで割り切れるサブセット


難易度 ハード
よく聞かれる アルセシウム Cisco DEショウ ディレクティ エクスペディア ミントラ PayU
配列 動的計画法

問題文

問題「合計がmで割り切れるサブセット」は、非負の整数と整数mの配列が与えられていることを示しています。 ここで、合計がmで割り切れるサブセットがあるかどうかを確認する必要があります。 つまり、mで最頻値をとると、サブセットの合計は結果として0になるはずです。

合計がmで割り切れるサブセット

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

説明

値が{1,2}のサブセットの合計は、結果として3になります。 {2、4}も合計すると、結果として6になり、これも3で割り切れます。したがって、答えは真です。

アプローチ

そのため、同様の問題が発生しました。 サブセットの合計がターゲットの合計と等しい。 ただし、ここではサブセット和が特定の和に等しいかどうかを確認しませんが、サブセット和がmで割り切れるかどうかを確認する必要があります。 したがって、sum = m、2m、3m、..などのサブセットがあるかどうかを確認する必要があるため、問題を再構成できます。サブセットの合計が指定された値のいずれかに等しい場合。 trueを返します。それ以外の場合はfalseを返します。

だから、このように考える代わりに。 合計のモジュロを取り続け、どういうわけか0を取得した場合、合計がmで割り切れるサブセットが存在することは確かです。 しかし、その前に何かを気にする必要があります。 要素の数n> = m(modが取得される対象の数)の場合。 そうすれば、鳩の巣原理のために答えは常に存在します。 合計が0からm-1でn <= mの場合のみを処理する必要があります。

したがって、このアプローチの背後にある全体的な考え方は、sum = jを持つサブセットがいくつかあり、sum =(j + current_element)%mを持つ新しいサブセットを作成できるということです。 そして、それは私たちが私たちを埋める方法です 動的計画法 表。

コード

合計がmで割り切れるサブセットのC ++コード

#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で割り切れるサブセットのJavaコード

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テーブルを格納するためにのみ必要であったため、スペースの複雑さは線形です。