او (رقم) جاءِ ۾ سمري وارو مسئلو  


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب Amazon ڊارٽائي نرم
ڪيريو متحرڪ پروگرامنگ

مسئلي جو بيان  

"اي (سيٽ) خلا ۾ سبٽيوٽ رقم ٻڌائي ٿي ته توهان کي ڪجهه غير منفي انٽيگرز ۽ هڪ مخصوص قدر جي قطار ڏني وئي آهي. ھاڻي ڳوليو ته ڪوئي سبسٽ آھي جنھن جي رقم ڏنل ان پٽ ويليو جي برابر آھي.

مثال  

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

او (رقم) جاءِ ۾ سمري وارو مسئلوپن  

O (رقم) جڳهه ۾ سبسٽيٽ سم مسئلي لاءِ رستو  

سادو طريقو جيڪو ڪو به سوچي سگھي ٿو اهو آهي ته سڀني سبسڪيٽ ٺاهي ۽ انهن جي رقم وٺو. ھاڻي چيڪ ڪريو ته اھا رقم ڏنل انپٽ جي رقم جي برابر آھي ، صحيح؟ نقطه نظر صحيح آهي. ان ۾ ڪو شڪ نه آهي. پر هڪ مسئلو آهي ، اسان سڀني سبسيٽس کي موثر طريقي سان نٿا ٺاهي سگهون. سبسيٽس جي پيدائش خود O (2 ^ N) وقت جي پيچيدگي آهي. تنهن ڪري ، اسان کي ضرور ڪو ٻيو ضرور سوچڻ گهرجي ته مسئلو حل ڪيو وڃي.

ٺيڪ آهي ، اچو ته سوچون ته هن مسئلي کي هن طريقي سان. اسان thatاڻون ٿا ته ڪجھ سيٽون آھن ڪجھ رقمون. ھاڻي موجوده عنصر لاءِ ، اسان وٽ ٻه اختيار آھن يا ته اسين ان کي اڳ ۾ موجود موجود سبڪنٽس ۾ شامل ڪريون ٿا يا اسان ان کي ذيلي ذخيرو ۾ مشهوري نٿا ڪريون. تنهن ڪري ، هاڻي اسان knowاڻون ٿا ته اسان کي ڇا ڪرڻ گهرجي. ان کي مختصر ڪرڻ لاءِ ، اسان سمن تي لوپ هلائينداسين (جيڪا 1 کان انٽيپٽو سمس جي قدرن تي آهي). جتان اهو ٿورو پريشان ٿي رهيو آهي. اسان ان پائونٽ رقم کي ”ٽارگيٽ“ ۽ سٽيس جي نالي سان سڏيون ٿا جنهن کي موڙيو وڃي. اسان انهن سان ”آئي“ سان نمائندگي ڪنداسين. ۽ هر هڪ لاءِ ، اسين جانچ ڪندا آهيون جيڪڏهن موجوده عنصر کي نه وٺو ، “ڇا اسان وٽ هڪ سبٽ آهي ، جنهن جي مون جيت برابر آهي؟”. يا جيڪڏهن اسان اهو موجوده عنصر وٺون ته ان جي مجموعي رقم اسان جي برابر ٿي سگهي ٿي؟ تنهن ڪري اسان هن آخري بيان کي ٻيهر پڙهي سگهون ٿا. جيڪڏهن اسان مان هاڻوڪي عنصر جي قيمت کي رد ڪريون ٿا ، ڇا اسان وٽ هڪ موجوده سيٽ عنصر جي موجوده عنصر جي برابر رقم آهي؟

پڻ ڏسو
چيڪ ڪريو ته ڇا اهو سڌي لائين آهي ليٽ ڪوڊ جو حل

تنهن ڪري ، هاڻي اسان کي اهو ڳولهڻ جي ضرورت آهي ته ڇا اسان هڪ موجوده مان ايٽ يا برابر موجوده عنصر جي برابر رقم ٺاهيون ٿا.

هاڻي انهي کي ڪيئن حل ڪجي؟ اسان استعمال ڪنداسين متحرڪ پروگرامنگ هن مسئلي کي حل ڪرڻ لاءِ. اسان ٺاهي ڏينداسين 2 ڊي صف يا ميٽرڪ جنهن جي [i ، j] سيل صحيح آهي جيڪڏهن اسان 0 کان i تائين عناصر استعمال ڪندي j جي برابر رقم حاصل ڪري سگهون. ٻي صورت ۾ ، اهو غلط آهي.

اعلى فارمولا

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

ريورسل فارمولا مان ، اسان getاڻون ٿا ته موجوده قطار صرف آخري قطار تي منحصر آهي. تنهن ڪري اسان N عناصر لاءِ اين قطار جي بدران صرف ٻه قطار رکڻ سان پري ٿي وڃون ٿا. هڪ قطار آخري عنصر لاءِ قطار وانگر ڪم ڪندي ۽ ٻيو موجوده عنصر لاءِ. اهو هڪ مشهور پي ڊي اصلاح آهي.

ڪوڊ  

سي (+) خلا ۾ سبسيٽ سم مسئلي لاءِ سي (+) ڪوڊ

#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

جاوا ڪوڊ سب سيٽ سم واري مسئلي لاءِ او (رقم) خلا ۾

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 کان وٺي ڏنل انپٽ سيوم جي هر قيمت جي جانچ ڪئي آهي ته اها ممڪن آهي يا نه؟ ان ڪري وقت جي پيچيدگي پولونوميل آهي.

پڻ ڏسو
بي ترتيب ڏنل گراف لاءِ BFS

خلائي پيچيدگي

اي (سم) ، ڇاڪاڻ ته اسان هر عنصر لاءِ قطار استعمال نه ڪئي آهي. انهي جي بدران اسان صرف موجوده ۽ آخري عنصر لاءِ انٽرميڊيٽ نتيجا محفوظ ڪرڻ لاءِ صرف ٻه قطارن کي استعمال ڪيو آهي. اھڙيءَ طرح خلائي پيچيدگي سڌي آھي.