အို (ပေါင်းလဒ်) အာကာသအတွင်း Subset Sum ပြProbleနာ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Drishti-Soft
အခင်းအကျင်း Dynamic Programming

ပြProbleနာဖော်ပြချက်

“ O (sum) space in space”) ပြproblemနာရဲ့ပြသနာကသင်ဟာအနုတ်လက္ခဏာမဟုတ်သောကိန်းဂဏန်းများနှင့်သတ်သတ်မှတ်မှတ်တန်ဖိုးတစ်ခုကိုပေးသည်ဟုဖော်ပြသည်။ စုစုပေါင်းပမာဏသည်ပေးထားသောတန်ဖိုးတန်ဖိုးနှင့်ညီမျှသောအမျိုးအစားခွဲတစ်မျိုးရှိမရှိယခုစစ်ဆေးပါ။

နမူနာ

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

အို (ပေါင်းလဒ်) အာကာသအတွင်း Subset Sum ပြProbleနာ

အို (ပေါင်းလဒ်) အာကာသအတွင်း Subset Sum ပြmနာများအတွက်ချဉ်းကပ်မှု

မည်သူမဆိုစဉ်းစားနိုင်သည့်အရိုးရှင်းဆုံးချဉ်းကပ်မှုသည် subsets အားလုံးကို ဖန်တီး၍ ၎င်းတို့ကိုပေါင်းခြင်းဖြစ်သည်။ အခုဒီပေါင်းလဒ်သည်ပေးထားသောသွင်းအားစုနဲ့ညီလားဆိုတာစစ်ကြည့်ပါ။ ဟုတ်သလား။ အဆိုပါချဉ်းကပ်မှုမှန်ကန်သည်။ သံသယဖြစ်စရာမရှိပါဘူး။ သို့သော်ပြproblemနာတစ်ခုရှိသည်၊ ကျွန်ုပ်တို့သည်အစိတ်အပိုင်းများအားလုံးကိုထိရောက်စွာမဖန်တီးနိုင်ပါ။ subsets ကိုယ်နှိုက်၏ဖန်တီးမှုအို (2 ^ N) အချိန်ရှုပ်ထွေးရှိပါတယ်။ ဒါ့ကြောင့်ပြtheနာကိုဖြေရှင်းဖို့အခြားထိရောက်တဲ့နည်းလမ်းတစ်ခုကိုစဉ်းစားရမယ်။

အိုကေ၊ ဒီပြproblemနာကိုဒီနည်းနဲ့စဉ်းစားကြည့်ရအောင်။ အချို့သောအစိတ်အပိုင်းများရှိသည့်အချို့သောအစိတ်အပိုင်းများရှိကြောင်းကျွန်ုပ်တို့သိသည်။ အခုလက်ရှိဒြပ်စင်အတွက်ကျွန်ုပ်တို့တွင်ရွေးစရာနှစ်ခုရှိသေးသည်။ ၎င်းကိုလက်ရှိရှိပြီးသားအစိတ်အပိုင်းများထဲသို့ထည့်သည်သို့မဟုတ်၎င်းကို subsets များထဲသို့မထည့်ပါ။ ဒီတော့အခုကျွန်တော်တို့ဘာလုပ်ဖို့လိုအပ်တယ်ဆိုတာသိပြီ။ ဒါကိုအတိုချုပ်ပြောရရင်ကျွန်တော်တို့ဟာခုနက (1 မှ input sum အထိတန်ဖိုးများ) တွင် loop တစ်ခုကိုအသုံးပြုမည်ဖြစ်သည်။ ဒီနည်းနည်းရှုပ်ထွေးလာပြီဖြစ်ပါတယ်ကတည်းက။ Input sum ကို“ Target” လို့ခေါ်ပြီးဖြတ်သန်းရမယ့်ပမာဏ။ သူတို့ကိုငါ“ i” နဲ့ကိုယ်စားပြုလိမ့်မယ်။ ပြီးတော့ i တစ်ခုစီအတွက်လက်ရှိ element ကိုမယူဘူးလားဆိုတာစစ်ဆေးသည် -“ ငါမှာ i နဲ့ညီတဲ့အစုတစ်ခုရှိသလား။ ” ။ ဒါမှမဟုတ်အခုဒီ element ကိုယူလျှင်စုစုပေါင်းစုစုပေါင်းသည် i ၏တန်ဖိုးနှင့်ညီနိုင်သလား။ ဒါကြောင့်ကျနော်တို့ကဒီနောက်ဆုံးကြေညာချက်ပြန်ပြီးနိုင်ပါတယ်။ အကယ်၍ ကျွန်ုပ်တို့သည်လက်ရှိ element ၏တန်ဖိုးကို i မှနုတ်ပါကကျွန်ုပ်သည် i-current element ၏တန်ဖိုးနှင့်ညီမျှသောအစိတ်အပိုင်းတစ်ခုရှိပါသလား။

ဒီတော့အခုငါတို့ i သည်တူသောသို့မဟုတ် i-current ဒြပ်စင်နှင့်ညီမျှသောအစုတစ်စုကိုဖွဲ့စည်းနိုင်မနိုင်ရှာဖွေရန်လိုအပ်သည်။

အခုဘယ်လိုဖြေရှင်းရမလဲ။ ငါတို့သုံးမယ် Dynamic Programming ဒီပြproblemနာကိုဖြေရှင်းဖို့။ 2D array သို့မဟုတ် matric တစ်ခုကိုဖန်တီးလိမ့်မည်။ အကယ်၍ ကျွန်ုပ်တို့သည် 0 မှ i သို့ element များကို အသုံးပြု၍ j နှင့်ညီမျှသော subset ကိုရနိုင်လျှင် [i, j] cell သည်မှန်ကန်သည်။ ဒီလိုမှမဟုတ်ရင်ဒါဟာမှားယွင်းတဲ့ဖြစ်ပါတယ်။

Recursive ပုံသေနည်း

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

recursive ဖော်မြူလာမှလက်ရှိအတန်းသည်နောက်ဆုံးအတန်းပေါ်တွင်သာမူတည်ကြောင်းကျွန်ုပ်တို့သိလာကြသည်။ ဒါကြောင့် n element တွေအတွက် n အတန်းအစား ၂ တန်းလောက်ပဲထားလို့ရတယ်။ row တစ်ခုသည်နောက်ဆုံး element အတွက် row တစ်ခုနှင့်လက်ရှိ element အတွက် row တစ်ခုကဲ့သို့လုပ်ဆောင်လိမ့်မည်။ ၎င်းသည်လူသိများသော DP optimization ဖြစ်သည်။

ကုဒ်

O (ပေါင်းလဒ်) အာကာသအတွင်း Subset Sum ပြmနာများအတွက် 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

Subset Sum Problem အတွက် 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (Sum * N)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ element တွေအားလုံးကိုဖြတ်ကျော်ပြီး ၀ ရဲ့သုညတန်ဖိုးကနေပေးထားတဲ့ input sum အထိဖြစ်နိုင်မလားဆိုတာကိုစစ်ဆေးပြီးဘာကြောင့်လဲ။ ဒီတော့အချိန်ရှုပ်ထွေးမှုက polynomial ဖြစ်တယ်။

အာကာသရှုပ်ထွေးမှု

အို (Sum)၊ ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ element တစ်ခုစီအတွက် rows ကိုမသုံးကြဘူးလေ။ အဲဒါကိုလုပ်မယ့်အစားလက်ရှိနဲ့နောက်ဆုံး element အတွက်အလယ်အလတ်ရလာဒ်တွေကိုသိုလှောင်ဖို့အတန်းနှစ်တန်းလောက်ပဲအသုံးပြုခဲ့တယ်။ ထို့ကြောင့်အာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။