סובסעט סאַם פּראָבלעם אין אָ (סומע) פּלאַץ


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן דרישטי-סאָפט
מענגע דינאַמיש פּראָגראַממינג

פּראָבלעם סטאַטעמענט

די "סובסעט סאַכאַקל אין אָ (סומע) פּלאַץ" פּראָבלעם שטאַטן אַז איר האָט אַ פּלאַץ פון עטלעכע נעגאַטיוו נעגאַטיווז און אַ ספּעציפיש ווערט. איצט געפֿינען אויס אויב עס איז אַ סאַבסעט וועמענס סומע איז גלייַך צו די געגעבן ינפּוט ווערט.

בייַשפּיל

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

סובסעט סאַם פּראָבלעם אין אָ (סומע) פּלאַץ

צוגאַנג פֿאַר סובסעט סאַם פּראָבלעם אין אָ (סומע) פּלאַץ

די סימפּלאַסט צוגאַנג וואָס ווער עס יז קענען טראַכטן פון איז צו מאַכן אַלע סובסעץ און נעמען די סומע. איצט טשעק אויב די סומע איז גלייַך צו די געגעבן אַרייַנשרייַב סומע, רעכט? דער צוגאַנג איז ריכטיק. עס איז קיין צווייפל וועגן דעם. אָבער עס איז איין פּראָבלעם, מיר קענען נישט מאַכן אַלע די סובסעץ יפישאַנטלי. די שאַפונג פון סובסעץ זיך האט אָ (2 ^ ן) צייט קאַמפּלעקסיטי. מיר מוזן טראַכטן וועגן אַן אנדערע עפעקטיוו וועג צו סאָלווע די פּראָבלעם.

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

איצט, מיר נאָר דאַרפֿן צו געפֿינען אויב מיר קענען פאָרעם אַ סאַבסעט מיט די סומע גלייַך צו i אָדער גלייַך צו די י-קראַנט עלעמענט.

איצט ווי צו סאָלווע עס? מיר וועלן נוצן דינאַמיש פּראָגראַממינג צו סאָלווע דעם פּראָבלעם. מיר וועלן שאַפֿן אַ 2 ד מענגע אָדער אַ מאַטריק וועמענס [i, j] צעל איז אמת אויב מיר קענען באַקומען אַ סאַבסעט מיט סומע גלייַך צו j ניצן עלעמענטן פֿון 0 צו i. אַנדערש, עס איז פאַלש.

רעקורסיווע פאָרמולע

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

פֿון די רעקורסיווע פאָרמולע, מיר וויסן אַז די קראַנט רודערן איז בלויז אָפענגיק אויף די לעצטע רודערן. אַזוי מיר קענען באַקומען אַוועק בלויז צוויי ראָוז אַנשטאָט N ראָוז פֿאַר N עלעמענטן. איין ריי וועט שפּילן ווי אַ ריי פֿאַר די לעצטע עלעמענט און די אנדערע פֿאַר דעם קראַנט עלעמענט. דאָס איז אַ באַוווסט דפּ אַפּטאַמאַזיישאַן.

קאָדעקס

C ++ קאָד פֿאַר סובסעט סאַם פּראָבלעם אין אָ (סומע) פּלאַץ

#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 קאָד פֿאַר סובסעט סאַם פּראָבלעם אין אָ (סומע) פּלאַץ

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (סומע * ען), ווייַל מיר האָבן דורכגעקאָכט אַלע די עלעמענטן און אָפּגעשטעלט פֿאַר יעדער ווערט פון די סומע פון ​​0 צו די ינפּוט סומע, צי עס איז מעגלעך אָדער נישט? די קאַמפּלעקסיטי פון צייט איז אַזוי פּאַלינאָומיאַל.

ספעיס קאַמפּלעקסיטי

אָ (סאַם), ווייַל מיר האָבן נישט געניצט ראָוז פֿאַר יעדער עלעמענט. אַנשטאָט דאָס, מיר האָבן נאָר געוויינט צוויי ראָוז צו קראָם ינטערמידייט רעזולטאַטן פֿאַר דעם קראַנט און לעצט עלעמענט. אזוי, פּלאַץ קאַמפּלעקסיטי איז לינעאַר.