ຊຸດຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດທີ່ສາມາດແບ່ງປັນໄດ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ກູໂກ
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ຄະນິດສາດ

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

ບັນຫາ "ຄູ່ທີ່ສາມາດແບ່ງແຍກທີ່ໃຫຍ່ທີ່ສຸດ" ລະບຸວ່າທ່ານໄດ້ຮັບຫຼາຍອົງປະກອບທີ່ແຕກຕ່າງກັນ. ຊອກຫາຄວາມຍາວທີ່ໃຫຍ່ທີ່ສຸດທີ່ແຕ່ລະຊຸດຍ່ອຍມີສ່ວນປະກອບທີ່ໃຫຍ່ກວ່າໂດຍແຍກອອກຈາກສ່ວນປະກອບນ້ອຍກວ່າ.

ຍົກຕົວຢ່າງ

ຊຸດຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດທີ່ສາມາດແບ່ງປັນໄດ້

array = {1, 2, 4, 5, 8, 9, 16}
5

ຄໍາອະທິບາຍ

ຊຸດຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດແມ່ນ 1, 2, 4, 8, 16 ເຊິ່ງປະຕິບັດຕາມເງື່ອນໄຂທີ່ລະບຸໄວ້ໃນປັນຫາ. ເນື່ອງຈາກຄວາມຍາວຂອງຊຸດຍ່ອຍນີ້ແມ່ນ 5, ຄຳ ຕອບແມ່ນ 5.

ວິທີການ

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

ສະນັ້ນເພື່ອແກ້ໄຂບັນຫາຢ່າງມີປະສິດທິຜົນ. ພວກເຮົາພະຍາຍາມແຍກບັນຫາອອກເປັນບັນຫານ້ອຍໆ. ບັນຫາກ່າວວ່າຄູ່ທຸກຄູ່ຄວນພໍໃຈກັບສະພາບທີ່ຕົວເລກນ້ອຍກວ່າຄວນແບ່ງ ຈຳ ນວນທີ່ໃຫຍ່ກວ່າ. ສະນັ້ນ, ຖ້າພວກເຮົາຄິດກ່ຽວກັບມັນພວກເຮົາສາມາດຄິດຫາວິທີແກ້ໄຂທີ່ຄ້າຍຄືກັບບັນຫາ LIS. ອັນດັບຕໍ່ໆໄປທີ່ຍາວທີ່ສຸດ ບັນຫາເວົ້າວ່າເພື່ອຊອກຫາຄວາມຍາວຂອງກຸ່ມຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດເຊິ່ງມີຄວາມເປັນລະບຽບຮຽບຮ້ອຍ. ພວກເຮົາສາມາດເຮັດສິ່ງທີ່ຄ້າຍຄືກັນໂດຍໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ. ກ່ອນອື່ນ ໝົດ ພວກເຮົາຈະຈັດຮຽງແຖວ. ຫຼັງຈາກນັ້ນ ສຳ ລັບແຕ່ລະອົງປະກອບ, ພວກເຮົາຈະເຫັນອົງປະກອບທັງ ໝົດ ກ່ອນມັນແລະກວດເບິ່ງວ່າມີອົງປະກອບໃດ ໜຶ່ງ ແບ່ງແຍກອົງປະກອບປັດຈຸບັນນີ້. ຖ້າມີອົງປະກອບໃດ ໜຶ່ງ ແບ່ງແຍກອົງປະກອບປັດຈຸບັນ, ພວກເຮົາຮູ້ວ່າພວກເຮົາສາມາດເພີ່ມປັດຈຸບັນເຂົ້າໃນຊຸດຍ່ອຍນັ້ນ.

ດັ່ງນັ້ນພວກເຮົາສ້າງຂບວນ DP ທີ່ອົງປະກອບຂອງມັນ ໝາຍ ເຖິງຄວາມຍາວຂອງຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດເຊິ່ງມີອົງປະກອບປັດຈຸບັນເປັນອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດຂອງມັນ. ແລະຊຸດຍ່ອຍພໍໃຈກັບເງື່ອນໄຂທີ່ວາງໄວ້ໃນບັນຫາ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຍ່ອຍຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດທີ່ສາມາດແບ່ງປັນໄດ້

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

int largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();
    if(n==0)return 0;
    sort(nums.begin(), nums.end());
    int dp[n], ans = INT_MIN;
    for(int i=0;i<n;i++){
        dp[i] = 1;
        for(int j=i-1;j>=0;j--)
            if(nums[i]%nums[j] == 0){
                if((dp[j]+1)>dp[i]){
                    dp[i] = dp[j]+1;
                    ans = max(ans, dp[i]);
                }
            }
    }
    return ans;
}

int main(){
  int n;cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
  int len = largestDivisibleSubset(v);
  cout<<len<<endl;
}
7
1 2 4 5 8 9 16
5

ລະຫັດ Java ສຳ ລັບຊຸດຍ່ອຍທີ່ສາມາດແບ່ງປັນທີ່ໃຫຍ່ທີ່ສຸດ

import java.util.*;
class Main{
  
  static int largestDivisibleSubset(ArrayList<Integer> nums) {
      int n = nums.size();
      if(n==0)return 0;
      Collections.sort(nums);
      int dp[] = new int[n];
      int ans = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          dp[i] = 1;
          for(int j=i-1;j>=0;j--)
              if(nums.get(i)%nums.get(j) == 0){
                  if((dp[j]+1)>dp[i]){
                      dp[i] = dp[j]+1;
                      ans = Math.max(ans, dp[i]);
                  }
              }
      }
      return ans;
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> v = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      v.add(a);
    }
    int len = largestDivisibleSubset(v);
    System.out.println(len);
  	}
}
7
1 2 4 5 8 9 16
5

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (N ^ 2), ເນື່ອງຈາກວ່າໃນປັນຫາພວກເຮົາຈະຜ່ານທຸກສ່ວນປະກອບທີ່ມາກ່ອນອົງປະກອບປັດຈຸບັນ. ຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນ polynomial.

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

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ ນຳ ໃຊ້ຂບວນການຈັດເກັບຄ່າຕ່າງໆເປັນຕາຕະລາງ DP. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.