O (sum) സ്ഥലത്ത് സബ്സെറ്റ് തുക പ്രശ്നം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ദൃശ്യ-സോഫ്റ്റ്
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

“ഓ (സം) സ്‌പെയ്‌സിലെ സബ്‌സെറ്റ് തുക” പ്രശ്‌നം നിങ്ങൾക്ക് ചില നെഗറ്റീവ് ഇതര സംഖ്യകളുടെ ഒരു നിരയും ഒരു നിർദ്ദിഷ്ട മൂല്യവും നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. തന്നിരിക്കുന്ന ഇൻപുട്ട് മൂല്യത്തിന് തുല്യമായ ഒരു ഉപസെറ്റ് ഉണ്ടോ എന്ന് ഇപ്പോൾ കണ്ടെത്തുക.

ഉദാഹരണം

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

O (sum) സ്ഥലത്ത് സബ്സെറ്റ് തുക പ്രശ്നം

O (sum) സ്‌പെയ്‌സിലെ സബ്‌സെറ്റ് സം പ്രശ്‌നത്തിനായുള്ള സമീപനം

ആർക്കും ചിന്തിക്കാൻ കഴിയുന്ന ഏറ്റവും ലളിതമായ സമീപനം എല്ലാ ഉപസെറ്റുകളും സൃഷ്ടിച്ച് അവയുടെ തുക എടുക്കുക എന്നതാണ്. ഈ തുക തന്നിരിക്കുന്ന ഇൻപുട്ട് തുകയ്ക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, അല്ലേ? സമീപനം ശരിയാണ്. അതിൽ യാതൊരു സംശയവുമില്ല. എന്നാൽ ഒരു പ്രശ്നമുണ്ട്, ഞങ്ങൾക്ക് എല്ലാ ഉപസെറ്റുകളും കാര്യക്ഷമമായി സൃഷ്ടിക്കാൻ കഴിയില്ല. ഉപസെറ്റുകളുടെ സൃഷ്ടിക്ക് തന്നെ O (2 ^ N) സമയ സങ്കീർണ്ണതയുണ്ട്. അതിനാൽ, പ്രശ്നം പരിഹരിക്കാനുള്ള മറ്റ് കാര്യക്ഷമമായ മാർഗ്ഗങ്ങളെക്കുറിച്ച് നമ്മൾ ചിന്തിക്കണം.

ശരി, അതിനാൽ ഈ പ്രശ്നത്തെക്കുറിച്ച് നമുക്ക് ചിന്തിക്കാം. ചില തുകകളുള്ള ചില ഉപസെറ്റുകൾ ഉണ്ടെന്ന് ഞങ്ങൾക്കറിയാം. നിലവിലെ ഘടകത്തിനായി, ഞങ്ങൾക്ക് രണ്ട് ഓപ്ഷനുകളുണ്ട്, ഒന്നുകിൽ ഞങ്ങൾ ഇതിനകം നിലവിലുള്ള സബ്സെറ്റുകളിലേക്ക് ചേർക്കുന്നു അല്ലെങ്കിൽ ഞങ്ങൾ അത് സബ്സെറ്റുകളിൽ പരസ്യം ചെയ്യുന്നില്ല. അതിനാൽ, നമ്മൾ എന്താണ് ചെയ്യേണ്ടതെന്ന് ഇപ്പോൾ നമുക്കറിയാം. ചുരുക്കത്തിൽ, ഞങ്ങൾ തുകകൾക്ക് മുകളിൽ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കും (അത് 1 മുതൽ ഇൻപുട്ട് തുക വരെയുള്ള മൂല്യങ്ങളിൽ). ഇത് അൽപ്പം ആശയക്കുഴപ്പത്തിലായതിനാൽ. ഇൻ‌പുട്ട് തുകയെ “ടാർ‌ഗെറ്റ്” എന്നും ഞങ്ങൾ‌ സഞ്ചരിക്കേണ്ട തുകകൾ‌ എന്നും വിളിക്കുന്നു. “I” ഉപയോഗിച്ച് ഞങ്ങൾ അവരെ പ്രതിനിധീകരിക്കും. ഓരോ i നും, നിലവിലെ ഘടകം എടുക്കുന്നില്ലെങ്കിൽ ഞങ്ങൾ പരിശോധിക്കുന്നു, “എനിക്ക് തുല്യമായ ഒരു ഉപസെറ്റ് ഉണ്ടോ?”. അല്ലെങ്കിൽ ഈ നിലവിലെ ഘടകം എടുത്താൽ ആകെ തുക i യ്ക്ക് തുല്യമാക്കാമോ? അതിനാൽ ഈ അവസാന പ്രസ്താവന നമുക്ക് വീണ്ടും എഴുതാം. നിലവിലെ മൂലകത്തിന്റെ മൂല്യം i ൽ നിന്ന് കുറയ്ക്കുകയാണെങ്കിൽ, i- കറന്റ് എലമെന്റിന് തുല്യമായ തുകയുള്ള ഒരു ഉപസെറ്റ് നമുക്കുണ്ടോ?

അതിനാൽ, i- ന് തുല്യമായ അല്ലെങ്കിൽ i- നിലവിലെ ഘടകത്തിന് തുല്യമായ ഒരു ഉപസെറ്റ് രൂപീകരിക്കാൻ കഴിയുമോ എന്ന് ഇപ്പോൾ കണ്ടെത്തേണ്ടതുണ്ട്.

ഇപ്പോൾ അത് എങ്ങനെ പരിഹരിക്കും? ഞങ്ങൾ ഉപയോഗിക്കും ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ഈ പ്രശ്നം പരിഹരിക്കാൻ. 2 മുതൽ i വരെയുള്ള ഘടകങ്ങൾ ഉപയോഗിച്ച് j ന് തുല്യമായ ഒരു ഉപസെറ്റ് ലഭിക്കുമെങ്കിൽ [i, j] സെൽ ശരിയായ ഒരു 0D അറേ അല്ലെങ്കിൽ ഒരു മെട്രിക് ഞങ്ങൾ സൃഷ്ടിക്കും. അല്ലെങ്കിൽ, അത് തെറ്റാണ്.

ആവർത്തന ഫോർമുല

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

ആവർത്തന സൂത്രവാക്യത്തിൽ നിന്ന്, നിലവിലെ വരി അവസാന വരിയെ മാത്രം ആശ്രയിച്ചിരിക്കുന്നുവെന്ന് ഞങ്ങൾ മനസ്സിലാക്കുന്നു. അതിനാൽ n ഘടകങ്ങൾക്ക് n വരികൾക്ക് പകരം രണ്ട് വരികൾ മാത്രം സൂക്ഷിക്കുന്നതിലൂടെ നമുക്ക് രക്ഷപ്പെടാം. ഒരു വരി അവസാന ഘടകത്തിന് ഒരു വരിയായും മറ്റൊന്ന് നിലവിലെ ഘടകത്തിന് ഒരു വരിയായും പ്രവർത്തിക്കും. ഇത് അറിയപ്പെടുന്ന ഡിപി ഒപ്റ്റിമൈസേഷനാണ്.

കോഡ്

O (sum) സ്‌പെയ്‌സിലെ സബ്‌സെറ്റ് സം പ്രശ്‌നത്തിനായുള്ള 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

O (sum) സ്‌പെയ്‌സിലെ സബ്‌സെറ്റ് സം പ്രശ്‌നത്തിനായുള്ള ജാവ കോഡ്

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 (തുക), കാരണം ഓരോ ഘടകത്തിനും ഞങ്ങൾ വരികൾ ഉപയോഗിച്ചിട്ടില്ല. അത് ചെയ്യുന്നതിനുപകരം നിലവിലുള്ളതും അവസാനവുമായ ഘടകത്തിനായി ഇന്റർമീഡിയറ്റ് ഫലങ്ങൾ സംഭരിക്കുന്നതിന് ഞങ്ങൾ രണ്ട് വരികൾ ഉപയോഗിച്ചു. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.