תת קבוצה זוגית הניתנת לחלוקה הגדולה ביותר


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית 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

ניתוח מורכבות

מורכבות זמן

O (N ^ 2), כי בבעיה אנו חוצים את כל האלמנטים שבאו לפני האלמנט הנוכחי. מורכבות הזמן היא פולינומית.

מורכבות בחלל

O (N) מכיוון שהשתמשנו במערך לאחסון הערכים כטבלת DP. מורכבות החלל היא לינארית.