ເຄື່ອງຍ່ອຍທີ່ມີຜົນບວກແບ່ງອອກໂດຍມ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Arcesium Cisco DE Shaw Directi Expedia Myntra PayU
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

ບັນຫາ "Subset ດ້ວຍຜົນລວມທີ່ສາມາດແບ່ງປັນໄດ້ໂດຍ m" ລະບຸວ່າທ່ານໄດ້ຖືກມອບໃຫ້ຕົວເລກຂອງຕົວເລກທີ່ບໍ່ແມ່ນລົບແລະຕົວເລກ m. ຕອນນີ້ທ່ານ ຈຳ ເປັນຕ້ອງຊອກຮູ້ວ່າມີຊຸດຍ່ອຍທີ່ມີຜົນບວກທີ່ສາມາດແບ່ງແຍກໄດ້ໂດຍ m. ນັ້ນແມ່ນຜົນລວມຂອງຂໍ້ຍ່ອຍຄວນໃຫ້ 0 ເປັນຜົນເມື່ອພວກເຮົາເອົາຮູບແບບຂອງມັນກັບ m.

ຍົກຕົວຢ່າງ

ເຄື່ອງຍ່ອຍທີ່ມີຜົນບວກແບ່ງອອກໂດຍມ

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

ຄໍາອະທິບາຍ

ເຄື່ອງຍ່ອຍທີ່ມີຄ່າ {1,2} ລວມເພື່ອໃຫ້ 3 ເປັນຜົນ. {2, 4} ຍັງສະຫຼຸບໃຫ້ 6 ເຊິ່ງເປັນຜົນທີ່ສາມາດແບ່ງປັນໄດ້ໂດຍ 3. ດັ່ງນັ້ນ ຄຳ ຕອບກໍ່ແມ່ນຄວາມຈິງ.

ວິທີການ

ດັ່ງນັ້ນ, ພວກເຮົາຍັງໄດ້ພົບກັບບັນຫາທີ່ຄ້າຍຄືກັນນີ້ເຊິ່ງເປັນການກວດສອບວ່າ ຜົນບວກຂອງການຍ່ອຍແມ່ນເທົ່າກັບ Sum ເປົ້າ ໝາຍ. ແຕ່ໃນທີ່ນີ້ບໍ່ໄດ້ກວດເບິ່ງວ່າຜົນບວກລວມເທົ່າກັບ ຈຳ ນວນທີ່ ກຳ ນົດໃຫ້ແຕ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງກວດເບິ່ງວ່າ ຈຳ ນວນຍ່ອຍທີ່ສາມາດແບ່ງແຍກໄດ້ໂດຍ m. ສະນັ້ນພວກເຮົາສາມາດປັບປຸງແກ້ໄຂບັນຫາດັ່ງທີ່ພວກເຮົາຕ້ອງການເພື່ອຊອກຫາວ່າມີ subset ມີ sum = m, 2m, 3m, .. , ແລະອື່ນໆ. ພວກເຮົາກັບຄືນມາຄວາມຈິງອື່ນທີ່ບໍ່ຖືກຕ້ອງ.

ສະນັ້ນ, ແທນທີ່ຈະຄິດແບບນີ້. ພວກເຮົາສືບຕໍ່ເອົາ mod ຂອງ sum ແລະຖ້າພວກເຮົາໄດ້ຮັບ 0. ພວກເຮົາແນ່ໃຈວ່າມີຕົວເລກຍ່ອຍທີ່ມີຜົນບວກແບ່ງອອກໂດຍ m. ແຕ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງເອົາໃຈໃສ່ບາງສິ່ງບາງຢ່າງກ່ອນນັ້ນ. ຖ້າ ຈຳ ນວນຂອງອົງປະກອບ n> = m (ຈຳ ນວນທຽບໃສ່ກັບ mod ໃດທີ່ຈະເອົາໄປ). ແລ້ວ ຄຳ ຕອບກໍ່ມີຢູ່ສະ ເໝີ ເພາະວ່າ Pigeonhole Principle. ພວກເຮົາພຽງແຕ່ຕ້ອງການແກ້ໄຂບັນດາກໍລະນີທີ່ມີຜົນບວກ 0 ເຖິງ m-1 ເຊິ່ງແມ່ນ n <= m.

ດັ່ງນັ້ນ, ຄວາມຄິດທັງ ໝົດ ທີ່ຢູ່ເບື້ອງຫຼັງວິທີການນີ້ແມ່ນວ່າພວກເຮົາມີບາງຊຸດຍ່ອຍທີ່ມີ sum = j, ຫຼັງຈາກນັ້ນພວກເຮົາສາມາດສ້າງ subset ໃໝ່ ມີ sum = (j + current_element)% m. ແລະນັ້ນແມ່ນວິທີທີ່ພວກເຮົາຈະຕື່ມຂໍ້ມູນໃສ່ພວກເຮົາ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ຕາຕະລາງ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບ Subset ດ້ວຍຜົນບວກທີ່ແບ່ງອອກໂດຍ 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 ສຳ ລັບ Subset ດ້ວຍຜົນລວມທີ່ແບ່ງອອກໂດຍ 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. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນ polynomial.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (M), ເນື່ອງຈາກວ່າພື້ນທີ່ທີ່ຕ້ອງການ ສຳ ລັບແຖວ dp ແມ່ນເສັ້ນຊື່. ຕ້ອງການພື້ນທີ່ພຽງແຕ່ ສຳ ລັບການເກັບຮັກສາຕາຕະລາງ dp ແລະດັ່ງນັ້ນຄວາມສັບສົນຂອງພື້ນທີ່ຈຶ່ງເປັນເສັ້ນ.