סכום זוגות מרבי עם הבדל ספציפי


רמת קושי קַל
נשאל לעתים קרובות נאמן Coursera מסירה פורקיטים Snapdeal
מערך תכנות דינמי

הבעיה "סכום מקסימלי של זוגות עם הבדל ספציפי" קובעת שקיבלתם מערך של מספרים שלמים ומספר שלם K. ואז אנו מתבקשים לברר את הסכום המרבי של זוגות עצמאיים. אנו יכולים לזווג שני מספרים שלמים אם יש להם הבדל מוחלט הנמוך מ- K. לכן אנו נדרשים למצוא את הסכום המרבי של זוגות x כאלה שהוא 2x מספרים.

דוגמה

סכום זוגות מרבי עם הבדל ספציפי

42, 43, 4, 5, 6, 12
96

הסבר

אנו בוחרים 42, 43 ו- 5, 6. היו לנו אפשרויות בין 4, 5 ו- 6. אז אנו לוקחים את הערך המקסימלי ביניהם מה שהופך את התוצאה = 96.

גישה

הבעיה מבקשת מאיתנו למצוא את הסכום המקסימלי שניתן להשיג אם נשייך כמה אלמנטים של ה- מערך. אנו יכולים לזווג אלמנטים בתנאי המוטל כי על היסודות להיות הבדל מוחלט של פחות מק 'לפני שנפתור את הבעיה, אנו sort המערך. בדרך זו אנו גוזמים את שטח החיפוש שלנו. שקול שהיה לנו מערך לא ממוין. אז נצטרך לחצות את כל האלמנטים לצורך התאמת אלמנט. אך לאחר המיון אנו יודעים שהאלמנט הגדול ביותר הוא רק האלמנט שהיה קודם לו. אז אנחנו בודקים אם התנאי מתקיים.

אם התנאי מתקיים, נשייך את האלמנט הקודם והנוכחי ונוסיף את התוצאה לבעיה עד האלמנט השני האחרון (מהאלמנט הנוכחי). אך אם התנאי אינו מתקיים. אנו עוזבים את הזיווג והתוצאה זהה לזו של עד האלמנט הקודם. באופן רשמי יותר, תוצאה [i] = תוצאה [i-2] + קלט [i] + קלט [i-2], אם ההתאמה נעשית אחרת התוצאה [i] = תוצאה [i-1]. כאן מערך התוצאות הזה הוא שלנו DP מערך כי אנו מאחסנים את התוצאה של תת-הבעיות הקטנות יותר. אנו משלבים את התוצאה של בעיות משנה קטנות יותר אלה כדי למצוא את התוצאה של הבעיה המקורית כפי שאנו עושים ב- DP מלמטה למעלה.

קופונים

קוד C ++ כדי למצוא את הסכום המרבי של זוגות עם הבדל ספציפי

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

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

קוד Java כדי למצוא את הסכום המרבי של זוגות עם הבדל ספציפי

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

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

מורכבות זמן 

O (NlogN), הסיבה לכך היא שמיינו את המערך בתחילה. ומיזוג מיונים ואלגוריתמי מיון אחרים יכולים למיין את המערך ב- O (NlogN). אם היו מספקים לנו קלט ממוין היינו יכולים לפתור את הבעיה בזמן O (N).

מורכבות בחלל

O (N) שטח זה נדרש למיון המערך. גם אם לא היינו יוצרים את מערך ה- DP והיינו משתמשים באותו מערך קלט לטבלת DP. לפיתרון זה יש עדיין אותה מורכבות שטח משום שמרחב זה נדרש למיון.