O (нийлбэр) орон зайд дэд нийлбэрийн асуудал  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Дришти-Зөөлөн
Array Динамик програмчлал

Асуудлын мэдэгдэл  

“O (sum) space дахь дэд олонлогийн нийлбэр” бодлогод танд зарим сөрөг бус бүхэл тоон массив болон тодорхой утга өгөгдсөн болохыг зааж өгсөн болно. Нийлбэр нь өгөгдсөн оролтын утгатай тэнцүү дэд хэсэг байгаа эсэхийг одоо олж мэдээрэй.

Жишээ нь  

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-ээс хасвал i-гүйдлийн элементийнхтэй тэнцүү нийлбэр бүхий дэд олонлог байна уу?

мөн үзнэ үү
Энэ нь шулуун шугамын Leetcode шийдэл мөн эсэхийг шалгана уу

Тиймээс одоо бид i-тэй тэнцүү эсвэл i-гүйдлийн элементтэй тэнцүү нийлбэр бүхий дэд олонлог үүсгэж чадах эсэхийг л олох хэрэгтэй.

Одоо үүнийг хэрхэн шийдэх вэ? Бид ашиглах болно Динамик програмчлал энэ асуудлыг шийдэх. бид 2-ээс i хүртэлх элементүүдийг ашиглан j-тэй тэнцүү дэд багц авч чадвал [i, j] нүд нь үнэн 0D массив эсвэл матриц үүсгэх болно. Үгүй бол энэ нь худлаа юм.

Рекурсив томъёо

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

Рекурсив томъёоноос бид одоогийн мөр нь зөвхөн сүүлийн мөрөөс хамааралтай болохыг олж мэднэ. Тиймээс n элементийн n мөрийн оронд зөвхөн хоёр мөр үлдээхээс зайлсхийх боломжтой. Нэг мөр нь сүүлчийн, нөгөө элемент нь одоогийн элементийн хувьд эгнээ шиг ажиллах болно. Энэ бол бидний сайн мэдэх АН-ын оновчлол юм.

код  

O (нийлбэр) орон зайд дэд олонлогийн асуудалд зориулсан 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) орон зайд дэд олонлогын асуудалд зориулсан 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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (Sum * N), Учир нь бид бүх элементүүдийг туулж, нийлбэрийн утга бүрийг 0-ээс өгөгдсөн оролтын нийлбэр хүртэл боломжтой эсэхийг шалгасан. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь олон гишүүнт юм.

мөн үзнэ үү
Салгасан графикийн BFS

Сансрын нарийн төвөгтэй байдал

O (Sum), Учир нь бид элемент тус бүрт мөр ашиглаагүй байна. Үүнийг хийхийн оронд бид одоогийн болон сүүлийн элементийн завсрын үр дүнг хадгалахын тулд хоёр мөрийг ашигласан болно. Тиймээс сансрын нарийн төвөгтэй байдал нь шугаман юм.