בעיית סכום משנה בקבוצת שטח O (סכום)


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית דרישטי-סופט
מערך תכנות דינמי

הצהרת בעיה

בעיית "סכום המשנה בסביבת O (סכום)" קובעת שקיבלתם מערך של מספר שלמים לא שלילי וערך ספציפי. עכשיו גלה אם יש תת קבוצה שסכומה שווה לסכום הערך הקלט הנתון.

דוגמה

Array = {1, 2, 3, 4}
targetSum = 7
The subset having sum equal to given input is possible

בעיית סכום משנה בקבוצת שטח O (סכום)

גישה לבעיית סכום תת קבוצה במרחב O (סכום)

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

אוקיי, אז בואו נחשוב על הבעיה הזו בצורה כזו. אנו יודעים שיש כמה קבוצות משנה שיש בהן סכומים. כעת עבור האלמנט הנוכחי, יש לנו שתי אפשרויות או שנוסיף אותו לקבוצות המשנה שכבר קיימות או שאנו לא מפרסמים אותו לקבוצות המשנה. אז, עכשיו אנחנו יודעים מה אנחנו צריכים לעשות. לסיכום, נפעיל לולאה על הסכומים (כלומר על הערכים מ -1 לסכום קלט). מכיוון שזה נהיה קצת מבלבל. אנו מכנים את סכום הקלט "יעד" ואת הסכומים שעליהם לעבור. נציג אותם עם "אני". ולכל i, אנו בודקים אם לא לוקחים את האלמנט הנוכחי, "האם יש לנו קבוצת משנה שיש לה סכום השווה ל- i?". או אם ניקח את האלמנט הנוכחי הזה האם נוכל להפוך את הסכום הכולל לשווה לזה של i? כדי שנוכל לנסח מחדש את ההצהרה האחרונה. אם נפחית את ערך האלמנט הנוכחי מ- i, האם יש לנו תת קבוצה שיש לה סכום השווה לזה של אלמנט i-current?

אז, עכשיו אנחנו רק צריכים למצוא אם אנחנו יכולים ליצור תת קבוצה שיש לה סכום שווה ל- i או שווה לאלמנט i-current.

עכשיו איך לפתור את זה? אנחנו נשתמש תכנות דינמי לפתור את הבעיה הזאת. ניצור מערך דו-ממדי או מטריצה ​​שתא ה- [i, j] שלהם נכון אם נוכל לקבל תת-קבוצה שיש בה סכום השווה ל- j באמצעות אלמנטים מ- 2 ל- i. אחרת, זה שקר.

נוסחה רקורסיבית

dp[i][j] = dp[i-1][j] | dp[i-1][j-input[i]]

מהנוסחה הרקורסיבית נוכל לדעת שהשורה הנוכחית תלויה רק ​​בשורה האחרונה. כדי שנוכל לחמוק משתי שורות בלבד במקום n שורות ל- n אלמנטים. שורה אחת תפעל כמו שורה עבור האלמנט האחרון והשנייה עבור האלמנט הנוכחי. זהו אופטימיזציה ידועה של DP.

קופונים

קוד C ++ עבור בעיית סכום תת קבוצה במרחב O (סכום)

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

#include <stdio.h>
#include <stdbool.h>

bool findSubset(int arr[], int n, int targetSum)
{
  // dp array to store if any sum is possible
  bool dp[2][targetSum + 1];

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= targetSum; j++) {

      // subset with sum equal to zero is always possible
      // we don't choose any element
      if (j == 0)
        dp[i % 2][j] = true;
      // j != 0 and i ==0
      else if (i == 0)
        dp[i % 2][j] = false;
      // current element is greater than the current value of sum(j)
      // so take OR of two conditions
      // 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
      // 2. We don't take the current element
      else if (arr[i - 1] <= j)
        dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j];
      // Here we cannot take the current element
      // So simply check is such a subset is possible
      else
        dp[i % 2][j] = dp[(i + 1) % 2][j];
    }
  }

  return dp[n % 2][targetSum];
}

int main(){
  // Number of elements
  int n;cin>>n;
  // array to store non-negative numbers
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  int targetSum;
  cin>>targetSum;
  bool can = findSubset(a, n, targetSum);
  if(can == true)
    cout<<"The subset having sum equal to given input is possible";
  else
    cout<<"None of the subsets have sum equal to given input";
}
4
1 2 3 4
6
The subset having sum equal to given input is possible

קוד Java עבור בעיית סכום תת קבוצה בחלל O (סכום)

import java.util.*;

class Main{
  
  static boolean findSubset(int arr[], int n, int targetSum) 
  { 
    // dp array to store if any sum is possible
    boolean dp[][] = new boolean[2][targetSum + 1];

    for (int i = 0; i <= n; i++) { 
      for (int j = 0; j <= targetSum; j++) { 

        // subset with sum equal to zero is always possibe
        // we don't choose any element
        if (j == 0) 
          dp[i % 2][j] = true; 
        // j != 0 and i ==0
        else if (i == 0) 
          dp[i % 2][j] = false;
        // current element is greater than the current value of sum(j)
        // so take OR of two conditions
        // 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
        // 2. We don't take the current element
        else if (arr[i - 1] <= j) 
          dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j]; 
        // Here we cannot take the current element
        // So simply check is such a subset is possible
        else
          dp[i % 2][j] = dp[(i + 1) % 2][j]; 
      } 
    }

    return dp[n % 2][targetSum]; 
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);

    // Number of elements
    int n = sc.nextInt();
    // array to store non-negative numbers
    int a[] = new int[n];
    for(int i=0;i<n;i++)
      a[i] = sc.nextInt();
    int targetSum = sc.nextInt();
    boolean can = findSubset(a, n, targetSum);
    if(can == true)
      System.out.println("The subset having sum equal to given input is possible");
    else
      System.out.println("None of the subsets have sum equal to given input");
  }
}
4
1 2 3 4
6
The subset having sum equal to given input is possible

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

מורכבות זמן

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

מורכבות בחלל

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