Ամենամեծ բաժանվող զույգը ենթաբազմություն


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Google
Դինամիկ ծրագրավորում Մաթեմատիկա

Խնդիրի հայտարարություն

«Ամենամեծ բաժանվող զույգերի ենթաբազմություն» խնդիրը նշում է, որ ձեզ տրվում է n հստակ տարրերի զանգված: Գտեք ամենամեծի երկարությունը այնպես, որ ենթաբազմության յուրաքանչյուր զույգ ունենա ավելի մեծ տարր `բաժանվող ավելի փոքր տարրերի:

Օրինակ

Ամենամեծ բաժանվող զույգը ենթաբազմություն

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

բացատրություն

Ամենամեծ ենթաբազմությունը 1, 2, 4, 8, 16-ն է, որը հետևում է խնդրում նշված պայմանին: Քանի որ այս ենթաբազմության երկարությունը 5 է, պատասխանը 5 է:

Մոտեցում

Սկսենք միամիտ մոտեցումից: Ամենապարզ բանը, որի մասին կարելի է մտածել, առաջացնել բոլոր ենթաբազմությունները և այնուհետև ստուգել, ​​արդյոք ենթաբազմությունը հետևում է տվյալ պայմանին: Եթե ​​այն պահում է, ապա պահիր ենթաբազմության երկարությունը: Շարունակեք թարմացնել այս արժեքը ավելի մեծ ենթաբազմության երկարությամբ, եթե գտնում եք որևէ մեկը, որը բավարարում է տվյալ պայմանը: Բայց այս մոտեցումը խիստ անարդյունավետ է, քանի որ այն պահանջում է բոլոր ենթաբազմությունների գեներացում, ինչը ինքնին պահանջում է ցուցիչ ժամանակ:

Այնպես որ, խնդիրը արդյունավետ լուծելու համար: Մենք փորձում ենք խնդիրը վերածել ավելի փոքր խնդիրների: Խնդիրն ասում է, որ բոլոր զույգերը պետք է բավարարեն այն պայմանը, որ փոքր թիվը պետք է բաժանի ավելի մեծ թիվը: Այսպիսով, եթե դրա մասին մտածենք, մենք կարող ենք մտածել այնպիսի լուծման մասին, որը նման է LIS- ի խնդրին: Ամենաերկար աճող հետևանքները խնդիրը ասում է գտնել ամենամեծ ենթախմբի երկարությունը, որն աճող կարգով է: Նման բան կարող ենք անել ՝ օգտագործելով Դինամիկ ծրագրավորում, Մենք նախ տեսակավորելու ենք զանգվածը: Այնուհետև յուրաքանչյուր տարրի համար մենք կտեսնենք դրա բոլոր տարրերը մինչ այդ և ստուգենք, թե արդյոք տարրերից որևէ մեկը բաժանում է այս ընթացիկ տարրը: Եթե ​​որևէ տարր բաժանում է ընթացիկ տարրը, մենք գիտենք, որ այդ ենթաբազմությանը կարող ենք ավելացնել ընթացիկ տարրը:

Այսպիսով, մենք ստեղծում ենք DP զանգված, որի ith տարրը նշանակում է ամենամեծ ենթախմբի երկարությունը, որն իր ամենամեծ տարրն ունի ընթացիկ տարրը: Եվ ենթաբազմությունը բավարարում է խնդրին դրված պայմանը:

Կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N ^ 2), քանի որ խնդրի մեջ մենք անցնում ենք բոլոր տարրերից, որոնք եկել են մինչև ընթացիկ տարրը: Timeամանակի բարդությունը բազմանդամ է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք արժեքներ պահելու համար զանգված ենք օգտագործել որպես DP աղյուսակ: Տիեզերական բարդությունը գծային է: